Posts tagged as “string”

花花酱 LeetCode 899. Orderly Queue

By zxi on September 1, 2018

Problem

A string S of lowercase letters is given. Then, we may make any number of moves.

In each move, we choose one of the first K letters (starting from the left), remove it, and place it at the end of the string.

Return the lexicographically smallest string we could have after any number of moves.

Example 1:

Input: S = "cba", K = 1
Output: "acb"
Explanation: 
In the first move, we move the 1st character ("c") to the end, obtaining the string "bac".
In the second move, we move the 1st character ("b") to the end, obtaining the final result "acb".

Example 2:

Input: S = "baaca", K = 3
Output: "aaabc"
Explanation: 
In the first move, we move the 1st character ("b") to the end, obtaining the string "aacab".
In the second move, we move the 3rd character ("c") to the end, obtaining the final result "aaabc".

Note:

1 <= K <= S.length <= 1000
S consists of lowercase letters only.

Solution: Rotation or Sort?

if \(k =1\), we can only rotate the string.

if \(k > 1\), we can bubble sort the string.

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string orderlyQueue(string S, int K) {

if (K > 1) {

sort(begin(S), end(S));

return S;

}

string ans = S;

for (int i = 1; i < S.size(); ++i)

ans = min(ans, S.substr(i) + S.substr(0, i));

return ans;

}

};

Java

// Author: Huahua

class Solution {

public String orderlyQueue(String S, int K) {

if (K > 1) {

char[] chars = S.toCharArray();

Arrays.sort(chars);

return new String(chars);

}

String ans = S;

for (int i = 1; i < S.length(); ++i) {

String tmp = S.substring(i) + S.substring(0, i);

if (tmp.compareTo(ans) < 0) ans = tmp;

}

return ans;

}

Python3 SC O(n^2)

# Author: Huahua 48 ms

class Solution:

def orderlyQueue(self, S, K):

if K > 1: return ''.join(sorted(S))

return min([S[i:] + S[0:i] for i in range(0, len(S))])

Python3 SC O(n)

# Author: Huahua 36 ms

class Solution:

def orderlyQueue(self, S, K):

if K > 1: return ''.join(sorted(S))

ans = S

for i in range(0, len(S)):

ans = min(ans, S[i:] + S[0:i])

return ans

花花酱 LeetCode 893. Groups of Special-Equivalent Strings

By zxi on August 26, 2018

Problem

You are given an array A of strings.

Two strings S and T are special-equivalent if after any number of moves, S == T.

A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].

Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.

Return the number of groups of special-equivalent strings from A.

Example 1:

Input: ["a","b","c","a","c","c"]
Output: 3
Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]

Example 2:

Input: ["aa","bb","ab","ba"]
Output: 4
Explanation: 4 groups ["aa"], ["bb"], ["ab"], ["ba"]

Example 3:

Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3
Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]

Example 4:

Input: ["abcd","cdab","adcb","cbad"]
Output: 1
Explanation: 1 group ["abcd","cdab","adcb","cbad"]

Note:

1 <= A.length <= 1000
1 <= A[i].length <= 20
All A[i] have the same length.
All A[i] consist of only lowercase letters.

Solution: Signature

All Special-Equivalent Strings should have the same signature if we sort all the odd-index characters and all the even-index characters.

E.g. [“abcd”,”cdab”,”adcb”,”cbad”] are all in the same graph.

“abcd”: odd “ac”, even: “bd”
“cdab”: odd “ac”, even: “bd”
“adcb”: odd “ac”, even: “bd”
“cbad”: odd “ac”, even: “bd”

We can concatenate the odd and even strings to create a hashable signature.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int numSpecialEquivGroups(vector<string>& A) {

unordered_set<string> s;

for (const string& a : A) {

string odd;

string even;

for (int i = 0; i < a.size(); ++i) {

if (i % 2)

odd += a[i];

else

even += a[i];

}

sort(begin(odd), end(odd));

sort(begin(even), end(even));

s.insert(odd + even);

}

return s.size();

}

};

Java

// Author: Huahua

// Running time: 16 ms

class Solution {

public int numSpecialEquivGroups(String[] A) {

Set<String> groups = new HashSet<>();

for (String a: A) {

char[] odd = new char[(a.length() + 1) / 2];

char[] even = new char[(a.length() + 1) / 2];

for (int i = 0; i < a.length(); ++i) {

if (i % 2 == 0)

even[i / 2] = a.charAt(i);

else

odd[i / 2] = a.charAt(i);

}

Arrays.sort(odd);

Arrays.sort(even);

String s = new String(odd) + new String(even);

groups.add(s);

}

return groups.size();

}

Python

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def numSpecialEquivGroups(self, A):

s = set()

for a in A:

odd = ""

even = ""

for i, c in enumerate(a):

if i % 2 == 0:

odd += c

else:

even += c

s.add(''.join(sorted(odd) + sorted(even)))

return len(s)

Python (1-linear)

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def numSpecialEquivGroups(self, A):

return len(set([''.join(sorted(a[0::2]) + sorted(a[1::2])) for a in A]))

花花酱 LeetCode 606. Construct String from Binary Tree

By zxi on August 22, 2018

Problem

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     

Output: "1(2(4))(3)"

Explanation: Originallay it needs to be "1(2(4)())(3()())", 
but you need to omit all the unnecessary empty parenthesis pairs. 
And it will be "1(2(4))(3)".

Example 2:

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 

Output: "1(2()(4))(3)"

Explanation: Almost the same as the first example, 
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

Solution: Recursion

Time complexity: O(n^2)

space complexity: O(n^2)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

string tree2str(TreeNode* t) {

if (!t) return "";

const string s = std::to_string(t->val);

// case 0: s

if (!t->left && !t->right)

return s;

// case 1: s(l)

if (!t->right)

return s + "(" + tree2str(t->left) + ")";

// general: s(l)(r)

return s + "(" + tree2str(t->left) + ")" + "(" + tree2str(t->right) + ")";

}

};

花花酱 LeetCode 890. Find and Replace Pattern

By zxi on August 19, 2018

Problem

You have a list of words and a pattern, and you want to know which words in words matches the pattern.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

(Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.)

Return a list of the words in words that match the given pattern.

You may return the answer in any order.

Example 1:

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,
since a and b map to the same letter.

Note:

1 <= words.length <= 50
1 <= pattern.length = words[i].length <= 20

Solution: Remember the last pos of each char.

Time complexity: O(n*l)

Space complexity: O(128) -> O(26)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

vector<string> findAndReplacePattern(vector<string>& words, string pattern) {

vector<string> ans;

for (const string& w : words)

if (match(w, pattern)) ans.push_back(w);

return ans;

}

private:

bool match(const string& w, const string& p) {

vector<int> last_pos_w(128, INT_MIN); // last pos of x in w

vector<int> last_pos_p(128, INT_MIN); // last pos of x in p

for (int i = 0; i < w.size(); ++i)

if (last_pos_w[w[i]] != last_pos_p[p[i]]) {

return false;

} else {

last_pos_w[w[i]] = last_pos_p[p[i]] = i;

}

return true;

}

};

花花酱 LeetCode 504. Base 7

By zxi on August 17, 2018

Problem

Given an integer, return its base 7 string representation.

Example 1:

Input: 100
Output: "202"

Example 2:

Input: -7
Output: "-10"

Note: The input will be in range of [-1e7, 1e7].

Solution: Simulation

Time complexity: O(logn)

Space complexity: O(logn)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string convertToBase7(int num) {

bool is_nagetive = num<0;

num = abs(num);

string ans;

do {

ans += ('0' + (num % 7));

num /= 7;

} while (num > 0);

if (is_nagetive)

ans += "-";

reverse(begin(ans), end(ans));

return ans;

}

};