IVN
0%

String好题

Posted on Edited on In
Symbols count in article: 24k Reading time ≈ 22 mins.

String好题选编

686. Repeated String Match

复制次数的下界和上界：

  • 对于「下界」的分析是容易的：至少将 a 复制长度大于等于 b 的长度，才有可能匹配。
  • 由于主串是由 a 复制多次而来，并且是从主串中找到子串 b，因此可以明确子串的起始位置，不会超过 a 的长度。

即长度越过 a 长度的起始匹配位置，必然在此前已经被匹配过了。

由此，我们可知复制次数「上界」最多为「下界 + 1」。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int repeatedStringMatch(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int ans = 0;
        while (sb.length() < b.length() && ++ans > 0) sb.append(a);
        sb.append(a);
        int idx = sb.indexOf(b);
        if (idx == -1) return -1;
        return idx + b.length() > a.length() * ans ? ans + 1 : ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode686 {
    public int repeatedStringMatch(String a, String b) {
        int n1=a.length();
        int n2=b.length();
        StringBuilder sb=new StringBuilder();
        int count=0;
        while(sb.length()<n2){
            sb.append(a);
            count++;
        }
        sb.append(a);
        count++;
        int i=sb.indexOf(b);
        if(i==-1){
            return -1;
        }
        return i+n2<=n1*(count-1) ? count-1 : count;
    }
}

730. Count Different Palindromic Subsequences

太难！

205. Isomorphic Strings

格式化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class LeetCode205 {
    public boolean isIsomorphic(String s, String t) {
        return convert(s).equals(convert(t));
    }

    String convert(String s){
        StringBuilder sb=new StringBuilder();
        Map<Character,Character> map=new HashMap<>();
        char[] arr = s.toCharArray();
        int l=1;
        int cur=0;
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]==arr[i-1]){
                if(i==1){
                    char c=(char)('a'+cur);
                    map.put(arr[i],c);
                    cur++;
                }
                l++;
            }else{
                if(!map.containsKey(arr[i])){
                    char c=(char)('a'+cur);
                    map.put(arr[i],c);
                    cur++;
                }
                sb.append(map.get(arr[i]));
                sb.append(l);
                sb.append(' ');
                l=1;
            }
        }
        if(!map.containsKey(arr[arr.length-1])){
            char c=(char)('a'+cur);
            map.put(arr[arr.length-1],c);
        }
        sb.append(map.get(arr[arr.length-1]));
        sb.append(l);
        return sb.toString();
    }
}

双表：

需要我们判断 s 和 t 每个位置上的字符是否都一一对应，即 s 的任意一个字符被 t 中唯一的字符对应，同时 t 的任意一个字符被 s 中唯一的字符对应。这也被称为「双射」的关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<Character, Character>();
        Map<Character, Character> t2s = new HashMap<Character, Character>();
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            char x = s.charAt(i), y = t.charAt(i);
            if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                return false;
            }
            s2t.put(x, y);
            t2s.put(y, x);
        }
        return true;
    }
}

290. Word Pattern

依葫芦画瓢，双表

注意：字符数和字符串数可能不等！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode290 {
    public boolean wordPattern(String pattern, String s) {
        Map<Character,String> p2s=new HashMap<>();
        Map<String,Character> s2p=new HashMap<>();
        String[] strings = s.split(" ");
        int i=0;
        int j=0;
        while (i<pattern.length() && j<strings.length) {
            char c=pattern.charAt(i);
            String str=strings[j];
            if(p2s.containsKey(c) && !p2s.get(c).equals(str) ||
            s2p.containsKey(str) && s2p.get(str)!=c){
                return false;
            }
            p2s.put(c,str);
            s2p.put(str,c);
            i++;
            j++;
        }
        return i==pattern.length() && j==strings.length ? true : false;
    }
}

91. Decode Ways

backtracking： Time Limit Exceeded

误区：

  • 无需用set考虑重复

    [i,i], s[i+1] 和 [i,i+1], s[i+2] 不可能相同，因为首字母就不一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Map<String,Character> map=new HashMap<>();
Set<String> set=new HashSet<>();
public int numDecodings(String s) {
    for (int i = 1; i <= 26; i++) {
        map.put(String.valueOf(i),(char)('A'+i-1));
    }
    backtracking(s,new LinkedList<>(),0);
    return set.size();
}

void backtracking(String s, LinkedList<Character> list, int i){
    if(i==s.length()){
        StringBuilder sb=new StringBuilder();
        for (char c : list) {
            sb.append(c);
        }
        set.add(sb.toString());
    }
    for (int j = i; j < i+2; j++) {
        //[i,j]
        if(i>=s.length()){
            break;
        }
        String sub=s.substring(i,j+1);
        if(map.containsKey(sub)){
            list.add(map.get(sub));
            backtracking(s,list,j+1);
            list.removeLast();
        }
    }
}

recursiveWithMemo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {

    Map<Integer, Integer> memo = new HashMap<>();

    public int numDecodings(String s) {
        return recursiveWithMemo(0, s);
    }
    
    private int recursiveWithMemo(int index, String str) {
        // Have we already seen this substring?
        if (memo.containsKey(index)) {
            return memo.get(index);
        }
        
        // If you reach the end of the string
        // Return 1 for success.
        if (index == str.length()) {
            return 1;
        }

        // If the string starts with a zero, it can't be decoded
        if (str.charAt(index) == '0') {
            return 0;
        }

        if (index == str.length() - 1) {
            return 1;
        }


        int ans = recursiveWithMemo(index + 1, str);
        if (Integer.parseInt(str.substring(index, index + 2)) <= 26) {
             ans += recursiveWithMemo(index + 2, str);
         }

        // Save for memoization
        memo.put(index, ans);

        return ans;
    }
}

Iterative Approach:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {

    public int numDecodings(String s) {
        // DP array to store the subproblem results
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        
        // Ways to decode a string of size 1 is 1. Unless the string is '0'.
        // '0' doesn't have a single digit decode.
        dp[1] = s.charAt(0) == '0' ? 0 : 1;

        for(int i = 2; i < dp.length; i++) {
            // Check if successful single digit decode is possible.
            if (s.charAt(i - 1) != '0') {
               dp[i] = dp[i - 1];  
            }
            
            // Check if successful two digit decode is possible.
            int twoDigit = Integer.valueOf(s.substring(i - 2, i));
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[s.length()];
    }
}

125. Valid Palindrome

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class LeetCode125 {
    public boolean isPalindrome(String s) {
        int n=s.length();
        int left=0;
        int right=n-1;
        while(left<right){
            while(left<right){
                char l=s.charAt(left);
                if(!Character.isAlphabetic(l)
                        && (l-'0'<0 || l-'0'>9)){
                    left++;
                }else{
                    break;
                }
            }
            if(left>=right){
                break;
            }
            while(left<right){
                char r=s.charAt(right);
                if(!Character.isAlphabetic(r)
                        && (r-'0'<0 || r-'0'>9)){
                    right--;
                }else{
                    break;
                }
            }
            if(left>=right){
                break;
            }
            if(Character.toLowerCase(s.charAt(left))!=Character.toLowerCase(s.charAt(right))){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

536. Construct Binary Tree from String

We usually utilize stack when we face problems related to parenthesis. And it’s time to do with the elements lying in the stack if we meet ‘)’.

In this case, the element we popped should be left child of the element on top of the stack if there is no left child yet, or else, it will be the right child.
Please note that if there is only one node, i.e., the root of the Binary Tree, then the element on top of the stack is the root. Or else, the pointer parent points to the root in the last.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public TreeNode str2tree(String s) {
    Deque<TreeNode> stack=new LinkedList<>();
    int i=0;
    int sign=1;
    TreeNode parent=null;
    TreeNode cur=null;
    while(i<s.length()){
        if(s.charAt(i)==')'){
            cur=stack.poll();
            parent=stack.peek();
            if(parent.left==null){
                parent.left=cur;
            }else{
                parent.right=cur;
            }
            i++;
        }else if(s.charAt(i)=='('){
            i++;
        }else if(s.charAt(i)=='-'){
            sign=-1;
            i++;
        }else{
            int num=0;
            while(i<s.length() && Character.isDigit(s.charAt(i))){
                num*=10;
                num+=s.charAt(i)-'0';
                i++;
            }
            TreeNode node=new TreeNode(sign*num);
            stack.push(node);
            sign=1;
        }
    }
    return stack.isEmpty() ? null :stack.peek();
}

97. Interleaving String

RTE: Brute Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public boolean is_Interleave(String s1, int i, String s2, int j, String res, String s3)
    {
        if(res.equals(s3) && i == s1.length() && j == s2.length())
            return true;
        boolean ans = false;
        if(i < s1.length())
            ans |= is_Interleave(s1, i + 1, s2, j, res + s1.charAt(i), s3);
        if(j < s2.length())
            ans |= is_Interleave(s1, i, s2, j + 1, res + s2.charAt(j), s3);
        return ans;

    }
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        return is_Interleave(s1, 0, s2, 0, "", s3);
    }
}

Approach 2: Recursion with memoization

注意：

  • 没必要存储当前String res，只需memo数组
  • 初始判断s1,s2,s3的length
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int[][] memo;
public boolean isInterleave(String s1, String s2, String s3) {
    //need to compare their length first
    if(s1.length()+s2.length()!=s3.length()){
        return false;
    }
    memo=new int[s1.length()][s2.length()];
    return dfs(s1,0,s2,0,s3,0);
}

boolean dfs(String s1, int i, String s2, int j, String s3, int k){
    if(i==s1.length()){
        return s2.substring(j).equals(s3.substring(k));
    }
    if(j==s2.length()){
        return s1.substring(i).equals(s3.substring(k));
    }
    if(memo[i][j]!=0){
        return memo[i][j]==1 ? true : false;
    }
    boolean res=false;
    if(i<s1.length() && s1.charAt(i)==s3.charAt(k)){
        res=res || dfs(s1,i+1,s2,j,s3,k+1);
    }
    if(j<s2.length() && s2.charAt(j)==s3.charAt(k)){
        res=res || dfs(s1,i,s2,j+1,s3,k+1);
    }
    memo[i][j]=res ? 1 : -1;
    return res;
}

Approach 3: Using 2D Dynamic Programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public boolean isInterleave(String s1, String s2, String s3) {
    if(s1.length()+s2.length()!=s3.length()){
        return false;
    }
    int n1=s1.length();
    int n2=s2.length();
    boolean[][] dp=new boolean[n1+1][n2+1];
    
    //use up every character => true
    for(int i=0; i<=n1; i++){
        for(int j=0; j<=n2; j++){
            if(i==0 && j==0){
                dp[i][j]=true;
            }else if(i==0){
                dp[i][j]=dp[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1);
            }else if(j==0){
                dp[i][j]=dp[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1);
            }else{
                dp[i][j]=dp[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1)
                    || dp[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1);
            }
        }
    }
    return dp[n1][n2];
}

Approach 4: Using 1D Dynamic Programming

151. Reverse Words in a String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public String reverseWords(String s) {
    //the sky is blue
    //eulb si yks eth
    //blue is sky the
    StringBuilder sb=new StringBuilder();
    s=s.trim();
    for (int i = 0; i < s.length(); i++) {
        sb.append(s.charAt(i));
    }
    String[] words = sb.reverse().toString().split("\\s+");
    sb=new StringBuilder();
    for (String word : words) {
        for (int i = word.length()-1; i >= 0; i--) {
            sb.append(word.charAt(i));
        }
        sb.append(" ");
    }
    sb.deleteCharAt(sb.length()-1);
    return sb.toString();
}

161. One Edit Distance

法一：一招鲜，计算最短距离，判断是否为1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean isOneEditDistance(String s, String t) {
    int n1=s.length();
    int n2=t.length();
    int[][] dp=new int[n1+1][n2+1];
    // 0 1 2 n2
    //0
    //n1
    for (int i = 0; i <= n1; i++) {
        dp[i][0]=i;
    }
    for (int j = 0; j <= n2; j++) {
        dp[0][j]=j;
    }
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if(s.charAt(i-1)==t.charAt(j-1)){
                dp[i][j]=dp[i-1][j-1];
            }else{
                dp[i][j]=Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
            }
        }
    }
    return dp[n1][n2]==1;
}

法二：分类讨论，one-pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public boolean isOneEditDistance(String s, String t) {
    int ns = s.length();
    int nt = t.length();

    // Ensure that s is shorter than t.
    if (ns > nt)
      return isOneEditDistance(t, s);

    // The strings are NOT one edit away distance  
    // if the length diff is more than 1.
    if (nt - ns > 1)
      return false;

    for (int i = 0; i < ns; i++)
      if (s.charAt(i) != t.charAt(i))
        // if strings have the same length
        if (ns == nt)
          return s.substring(i + 1).equals(t.substring(i + 1));
        // if strings have different lengths
        else
          return s.substring(i).equals(t.substring(i + 1));

    // If there is no diffs on ns distance
    // the strings are one edit away only if
    // t has one more character. 
    return (ns + 1 == nt);
  }
}

165. Compare Version Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int compareVersion(String version1, String version2) {
    //注意：regex中，"." means any character
    //"\\." means dot
    //"\\s+" means one or many space
    String[] arr1 = version1.split("\\.");
    String[] arr2 = version2.split("\\.");
    int i=0;
    while(i<arr1.length || i<arr2.length){
        int a= i<arr1.length ? Integer.parseInt(arr1[i]) : 0;
        int b= i<arr2.length ? Integer.parseInt(arr2[i]) : 0;
        if(a>b){
            return 1;
        }else if(a<b){
            return -1;
        }
        i++;
    }
    return 0;
}

166. Fraction to Recurring Decimal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public String fractionToDecimal(int numerator, int denominator) {
    //0
    if(numerator==0){
        return "0";
    }
    StringBuilder res=new StringBuilder();
    //positive or negative
    res.append((numerator>0)^(denominator>0) ? "" : "-");
    long num=Math.abs((long)numerator);
    long den=Math.abs((long)denominator);
    //integral part
    res.append(num/den); // 4/333
    num%=den;   //4
    if(num==0){
        return res.toString();
    }
    //fractional part
    res.append("."); //0.
    Map<Long,Integer> map=new HashMap<>();
    map.put(num,res.length());
    while(num!=0){
        num*=10;    //40
        res.append(num/den);    //0.0
        num%=den;   //40
        if(map.containsKey(num)){
            int index=map.get(num);
            res.insert(index,"(");
            res.append(")");
            break;
        }else{
            map.put(num,res.length());
        }
    }
    return res.toString();
}

179. Largest Number

edge cases:

  1. 3, 33
  2. 3, 32
  3. 3, 34
  4. 34323, 3432
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public String largestNumber(int[] nums) {
    int n=nums.length;
    String[] strs=new String[n];
    for (int i = 0; i < n; i++) {
        strs[i]=String.valueOf(nums[i]);
    }
    Arrays.sort(strs, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            //334 in front of 33
            //33 in front of 332
            if(o1.equals(o2)){
                return 0;
            }
            int count=0;
            int i=0;
            char a=o1.charAt(0);
            char b=o2.charAt(0);
            while(a==b){
                a=i<o1.length() ? o1.charAt(i) : o1.charAt(i%o1.length());
                b=i<o2.length() ? o2.charAt(i) : o2.charAt(i%o2.length());
                i++;
                count++;
                if(count>=50){
                    return 0;
                }
            }
            return a<b ? 1 : -1;
        }
    });
    StringBuilder sb=new StringBuilder();
    for (int i = 0; i < n; i++) {
        sb.append(strs[i]);
    }
    String res=sb.toString();
    return res.charAt(0)=='0' ? "0" : res;
}

186. Reverse Words in a String II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public void reverseWords(char[] s) {
    //the sky is blue
    //eulb si yks eht
    //blue is sky the
    int n=s.length;
    int l=0;
    int r=n-1;
    while(l<r){
        swap(s,l++,r--);
    }
    l=0;
    for (int i = 0; i < n; i++) {
        if(s[i]==' '){
            r=i-1;
            while(l<r){
                swap(s,l++,r--);
            }
            l=i+1;
        }
    }
    r=n-1;
    while(l<r){
        swap(s,l++,r--);
    }
}

void swap(char[] s, int l ,int r){
    char temp=s[l];
    s[l]=s[r];
    s[r]=temp;
}

187. Repeated DNA Sequences

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<String> findRepeatedDnaSequences(String s) {
    List<String> res=new ArrayList<>();
    Map<String,Integer> map=new HashMap<>();
    int n=s.length();
    for (int i = 0; i <= n-10; i++) {
        //[i,i+10)
        //[n-10,n)
        String cur=s.substring(i,i+10);
        map.put(cur,map.getOrDefault(cur,0)+1);
        if(map.get(cur)==2){
            res.add(cur);
        }
    }
    return res;
}

168. Excel Sheet Column Title

1
2
3
4
5
6
7
8
9
10
11
public String convertToTitle(int n) {
    //701=26*26+25 => ZY
    StringBuilder sb = new StringBuilder();
    while(n > 0){
        n--;
        int curr = n%26;
        n /= 26;
        sb.append((char)(curr+'A'));
    }
    return sb.reverse().toString();
}

171. Excel Sheet Column Number

1
2
3
4
5
6
7
8
9
10
11
12
13
public int titleToNumber(String columnTitle) {
           int res=0;
    int i=columnTitle.length()-1;
    int weight=1;
    while(i>=0){
        char c=columnTitle.charAt(i);
        int val=c-'A'+1;
        res+=val*weight;
        weight*=26;
        i--;
    }
    return res;
}

205. Isomorphic Strings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isIsomorphic(String s, String t) {
    return transform(s).equals(transform(t));
}

String transform(String s){
    StringBuilder sb=new StringBuilder();
    Map<Character,Character> map=new HashMap<>();
    int n=s.length();
    int k=0;
    for (int i = 0; i < n; i++) {
        char cur=s.charAt(i);
        if(!map.containsKey(cur)){
            map.put(cur,(char)('a'+k++));
        }
        sb.append(map.get(cur));
    }
    return sb.toString();
}

241. Different Ways to Add Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
HashMap<String,List<Integer>> map=new HashMap<>();
public List<Integer> diffWaysToCompute(String expression) {
    if(map.containsKey(expression)){
        return map.get(expression);
    }
    int n=expression.length();
    List<Integer> res=new ArrayList<>();
    for (int i = 0; i < n; i++) {
        char c=expression.charAt(i);
        if(c=='+' || c=='-' || c=='*'){
            String sub1=expression.substring(0,i);
            String sub2=expression.substring(i+1);
            List<Integer> list1=diffWaysToCompute(sub1);
            List<Integer> list2=diffWaysToCompute(sub2);
            for (Integer a : list1) {
                for (Integer b : list2) {
                    switch (c){
                        case '+':
                            res.add(a+b);
                            break;
                        case '-':
                            res.add(a-b);
                            break;
                        case '*':
                            res.add(a*b);
                            break;
                    }
                }
            }
        }
    }
    if(res.isEmpty()){
        res.add(Integer.valueOf(expression));
    }
    map.put(expression,res);
    return res;
}

242. Valid Anagram

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isAnagram(String s, String t) {
    if(s.length()!=t.length()){
        return false;
    }
    int n=s.length();
    int[] counts=new int[26];
    for (int i = 0; i < n; i++) {
        counts[s.charAt(i)-'a']++;
        counts[t.charAt(i)-'a']--;
    }
    for (int i = 0; i < 26; i++) {
        if(counts[i]!=0){
            return false;
        }
    }
    return true;
}

249. Group Shifted Strings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<List<String>> groupStrings(String[] strings) {
    Map<String, List<String>> map= new HashMap<>();
    for (String s : strings) {
        String t=transform(s);
        map.putIfAbsent(t,new LinkedList<>());
        map.get(t).add(s);
    }
    return new LinkedList<>(map.values());
}

String transform(String s){
    StringBuilder sb=new StringBuilder();
    int n=s.length();
    int shift=s.charAt(0)-'a';
    for (int i = 0; i < n; i++) {
        char c=s.charAt(i);
        //'z'=('a'+25)
        char t=(c-shift>='a') ? (char)(c-shift) : (char)(c-shift+26);
        sb.append(t);
    }
    return sb.toString();
}

266. Palindrome Permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean canPermutePalindrome(String s) {
    int[] arr=new int[26];
    int n=s.length();
    for (int i = 0; i < n; i++) {
        arr[s.charAt(i)-'a']++;
    }
    int c=0;
    for (int i = 0; i < 26; i++) {
        if((arr[i]&1)!=0){
            c++;
            if(c>1){
                return false;
            }
        }
    }
    return c<=1;
}

267. Palindrome Permutation II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
List<String> res=new ArrayList<>();
public List<String> generatePalindromes(String s) {
    int n=s.length();
    int[] arr=new int[26];
    for (int i = 0; i < n; i++) {
        arr[s.charAt(i)-'a']++;
    }
    boolean[] skip=new boolean[26];
    int c=0;
    for (int i = 0; i < 26; i++) {
        if((arr[i]&1)!=0){
            c++;
            if(c>1){
                return res;
            }
        }
        if(arr[i]==0){
            skip[i]=true;
        }
    }
    dfs(arr,skip,new char[n],0,n-1);
    return res;
}

void dfs(int[] arr, boolean[] skip, char[] chars, int left, int right){
    if(left>right){
        res.add(new String(chars));
        return;
    }
    if(left==right){
        for (int i = 0; i < 26; i++) {
            if(arr[i]==1){
                chars[left]=(char)('a'+i);
                res.add(new String(chars));
                return;
            }
        }
    }
    for (int i = 0; i < 26; i++) {
        if(skip[i] || arr[i]==0){
            continue;
        }
        if(arr[i]>=2){
            chars[left]=(char)('a'+i);
            chars[right]=(char)('a'+i);
            arr[i]-=2;
            dfs(arr,skip,chars,left+1,right-1);
            arr[i]+=2;
        }
    }
    
}

299. Bulls and Cows

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String getHint(String secret, String guess) {
    int a=0;    //bulls
    int b=0;    //cows
    int n=secret.length();
    int[] counts=new int[10];
    for (int i = 0; i < n; i++) {
        char c=secret.charAt(i);
        if(guess.charAt(i)==c){
            a++;
        }else{
            counts[c-'0']++;
        }
    }
    for (int i = 0; i < n; i++) {
        char c=guess.charAt(i);
        if(secret.charAt(i)!=c){
            if(counts[c-'0']>0){
                b++;
                counts[c-'0']--;
            }
        }
    }
    return a+"A"+b+"B";
}

290. Word Pattern

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    int n=words.length;
    if(pattern.length()!=n){
        return false;
    }
    Map<Character,String> map1=new HashMap<>();
    Map<String,Character> map2=new HashMap<>();

    for (int i = 0; i < n; i++) {
        String word=words[i];
        char c=pattern.charAt(i);
        if(map1.containsKey(c) && !map1.get(c).equals(word)){
            return false;
        }
        if(map2.containsKey(word) && map2.get(word)!=c){
            return false;
        }
        map1.put(c,word);
        map2.put(word,c);
    }
    return true;
}

291. Word Pattern II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public boolean wordPatternMatch(String pattern, String str) {
  Map<Character, String> map = new HashMap<>();
  Set<String> set = new HashSet<>();
  
  return isMatch(str, 0, pattern, 0, map, set);
}

boolean isMatch(String str, int i, String pat, int j, Map<Character, String> map, Set<String> set) {
  // base case
  if (i == str.length() && j == pat.length()) return true;
  if (i == str.length() || j == pat.length()) return false;
  
  // get current pattern character
  char c = pat.charAt(j);
  
  // if the pattern character exists
  if (map.containsKey(c)) {
    String s = map.get(c);
    
    // then check if we can use it to match str[i...i+s.length()]
    if (!str.startsWith(s, i)) {
      return false;
    }
    
    // if it can match, great, continue to match the rest
    return isMatch(str, i + s.length(), pat, j + 1, map, set);
  }
  
  // pattern character does not exist in the map
  for (int k = i; k < str.length(); k++) {
    String p = str.substring(i, k + 1);

    if (set.contains(p)) {
      continue;
    }

    // create or update it
    map.put(c, p);
    set.add(p);
    
    // continue to match the rest
    if (isMatch(str, k + 1, pat, j + 1, map, set)) {
      return true;
    }

    // backtracking
    map.remove(c);
    set.remove(p);
  }
  
  // we've tried our best but still no luck
  return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class LeetCode291 {
    Map<Character,String> map=new HashMap<>();
    Set<String> set=new HashSet<>();
    public boolean wordPatternMatch(String pattern, String s) {
        return match(pattern,s,0,0);
    }

    boolean match(String pattern, String s, int i, int j){
        if(i==pattern.length() && j==s.length()){
            return true;
        }
        if(i==pattern.length() || j==s.length()){
            return false;
        }
        char c=pattern.charAt(i);
        if(map.containsKey(c)){
            String word=map.get(c);
            //s[j,j+len-1]
            if(!s.startsWith(word,j)){
                return false;
            }
            return match(pattern,s,i+1,j+word.length());
        }
        for (int p = j; p < s.length(); p++) {
            //s[j,p]
            String next=s.substring(j,p+1);
            if(set.contains(next)){
                continue;
            }
            map.put(c,next);
            set.add(next);
            if(match(pattern,s,i+1,p+1)){
                return true;
            }
            map.remove(c);
            set.remove(next);
        }
        return false;
    }
}

316. Remove Duplicate Letters

好题！用stack和lastIndex数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public String removeDuplicateLetters(String s) {
    int[] lastIndex=new int[26];
    int n=s.length();
    for (int i = 0; i < n; i++) {
        lastIndex[s.charAt(i)-'a']=i;
    }
    boolean[] seen=new boolean[26];
    Deque<Character> stack=new LinkedList<>();
    for (int i = 0; i < n; i++) {
        char cur=s.charAt(i);
        if(seen[cur-'a']){
            continue;
        }
        while(!stack.isEmpty() && stack.peek()>cur && lastIndex[stack.peek()-'a']>i){
            seen[stack.pop()-'a']=false;
        }
        stack.push(cur);
        seen[cur-'a']=true;
    }
    StringBuilder sb=new StringBuilder();
    while(!stack.isEmpty()){
        sb.append(stack.pop());
    }
    return sb.reverse().toString();
}

318. Maximum Product of Word Lengths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int maxProduct(String[] words) {
    Arrays.sort(words,(a,b)->(a.length()-b.length()));
    int n=words.length;
    int res=0;
    for (int i = n-1; i > 0; i--) {
        String a=words[i];
        for (int j = i-1; j >= 0; j--) {
            String b=words[j];
            if(a.length()*b.length()<=res){
                break;
            }
            if(valid(a,b)){
                res=a.length()*b.length();
            }
        }
    }
    return res;
}

boolean valid(String a, String b){
    boolean[] seen=new boolean[26];
    for (int i = 0; i < a.length(); i++) {
        seen[a.charAt(i)-'a']=true;
    }
    for (int i = 0; i < b.length(); i++) {
        char c=b.charAt(i);
        if(seen[c-'a']){
            return false;
        }
    }
    return true;
}