IVN
0%

String好题(3)

Posted on Edited on In
Symbols count in article: 14k Reading time ≈ 13 mins.

String好题（3）

1268. Search Suggestions System

三吃，好题

Brute force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
    int n=searchWord.length();
    List<List<String>> res=new ArrayList<>();
    Arrays.sort(products);
    for (int i = 0; i < n; i++) {
        String cur=searchWord.substring(0,i+1);
        List<String> list=new ArrayList<>();
        int count=0;
        for (String p : products) {
            if(p.startsWith(cur)){
                list.add(p);
                count++;
                if(count==3){
                    break;
                }
            }
        }
        res.add(list);
    }
    return res;
}
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 List<List<String>> suggestedProducts(String[] products, String searchWord) {
    Arrays.sort(products);
    List<List<String>> res=new ArrayList<>();
    int start=0;
    int bStart=0;
    int n=products.length;
    for (int i = 0; i < searchWord.length(); i++) {
        String prefix=searchWord.substring(0,i+1);
        bStart=binary_search(products,prefix,start,n-1);
        List<String> list=new ArrayList<>();
        for (int j = bStart; j < n && list.size()<3; j++) {
            if(products[j].startsWith(prefix)){
                list.add(products[j]);
            }
        }
        start=bStart;
        res.add(list);
    }
    return res;
}

private int binary_search(String[] products, String prefix, int left, int right){
    while(left<right){
        int mid=(left+right)/2;
        if(products[mid].compareTo(prefix)<0){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left;
}

Trie

反而最慢

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
    Trie trie=new Trie();
    for (String product : products) {
        trie.insert(product);
    }
    List<List<String>> res=new ArrayList<>();
    for (int i = 0; i < searchWord.length(); i++) {
        res.add(trie.search(searchWord.substring(0,i+1)));
    }
    return res;
}

class Trie{
    Node root;
    boolean finished;
    Trie(){
        root=new Node();
    }

    List<String> search(String prefix){
        List<String> list=new ArrayList<>();
        finished=false;
        Node node=root;
        for (int i = 0; i < prefix.length(); i++) {
            char c=prefix.charAt(i);
            if(!node.children.containsKey(c)){
                return list;
            }
            node=node.children.get(c);
        }
        dfs(list,node);
        return list;
    }

    void dfs(List<String> list, Node cur){
        if(finished){
            return;
        }
        if(cur.word!=null){
            list.add(cur.word);
            if(list.size()==3){
                finished=true;
                return;
            }
        }
        for (Character c : cur.children.keySet()) {
            dfs(list,cur.children.get(c));
            if(finished){
                return;
            }
        }
    }

    void insert(String s){
        Node node=root;
        for (int i = 0; i < s.length(); i++) {
            char c=s.charAt(i);
            if(!node.children.containsKey(c)){
                node.children.put(c,new Node());
            }
            node=node.children.get(c);
        }
        node.word=s;
    }
}

class Node{
    String word;
    TreeMap<Character,Node> children;
    Node(){
        children=new TreeMap<>();
    }
}

1152. Analyze User Website Visit Pattern

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
public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
    Map<String,TreeMap<Integer,String>> map=new HashMap<>();
    int n=username.length;
    for (int i = 0; i < n; i++) {
        String user=username[i];
        String web=website[i];
        int time=timestamp[i];
        map.putIfAbsent(user,new TreeMap<>());
        map.get(user).put(time,web);
    }
    Map<String,Integer> count=new HashMap<>();
    for (String user : map.keySet()) {
        HashSet<String> set=new HashSet<>();
        List<String> list=new ArrayList<>(map.get(user).values());
        for (int i = 0; i < list.size(); i++) {
            for (int j = i+1; j < list.size(); j++) {
                for (int k = j+1; k < list.size(); k++) {
                    String s=list.get(i)+","+list.get(j)+","+list.get(k);
                    if(set.contains(s)){
                        continue;
                    }
                    set.add(s);
                    count.put(s,count.getOrDefault(s,0)+1);
                }
            }
        }
    }
    int max=0;
    String res=null;
    for (String s : count.keySet()) {
        int val=count.get(s);
        if(val>max){
            max=val;
            res=s;
        }else if(val==max && res.compareTo(s)>0){
            res=s;
        }
    }
    String[] split = res.split(",");
    List<String> list=new ArrayList<>();
    for (int i = 0; i < 3; i++) {
        list.add(split[i]);
    }
    return list;
}

2193. Minimum Number of Moves to Make Palindrome

太神了

https://leetcode.com/problems/minimum-number-of-moves-to-make-palindrome/discuss/1847011/c%2B%2B-2-pointers-with-detail-proof-and-explanation

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
public int minMovesToMakePalindrome(String s) {
    char[] chars = s.toCharArray();
    int n=chars.length;
    int l=0;
    int r=n-1;
    int center=-1;
    int res=0;
    while(l<r){
        if(chars[l]==chars[r]){
            l++;
            r--;
            continue;
        }
        int k=l+1;
        for(; k<r; k++){
            if(chars[k]==chars[r]){
                break;
            }
        }
        if(k==r){
            center=r;
            r--;
            continue;
        }
        for(int j=k; j>l; j--){
            swap(chars,j,j-1);
            res++;
        }
        l++;
        r--;
    }
    if(center!=-1){
        res+=center-n/2;
    }
    return res;
}

void swap(char[] chars, int i, int j){
    char temp=chars[i];
    chars[i]=chars[j];
    chars[j]=temp;
}

2222. Number of Ways to Select Buildings

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 long numberOfWays(String s) {
    long res=0;
    char[] chars = s.toCharArray();
    int n=s.length();
    long[] zos=new long[n];   //number of "10"s in [0,i]
    long[] ozs=new long[n];   //number of "01"s in [0,i]
    int[] zs=new int[n];    //number of "0"s in [0,i]
    int[] os=new int[n];    //number of "1"s in [0,i]
    zs[0]=chars[0]=='0' ? 1 : 0;
    os[0]=chars[0]=='1' ? 1 : 0;
    for (int i = 1; i < n; i++) {
        if(chars[i]=='0'){
            zs[i]=zs[i-1]+1;
            os[i]=os[i-1];
            //111 0
            ozs[i]=os[i-1]+ozs[i-1];
            zos[i]=zos[i-1];
            //01 0
            res+=zos[i-1];
        }else{
            zs[i]=zs[i-1];
            os[i]=os[i-1]+1;
            //000 1
            zos[i]=zs[i-1]+zos[i-1];
            ozs[i]=ozs[i-1];
            //10 1
            res+=ozs[i-1];
        }
    }
    return res;
}

2268. Minimum Number of Keypresses

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
public int minimumKeypresses(String s) {
    int n=s.length();
    int res=0;
    int[] arr=new int[26];
    for (int i = 0; i < n; i++) {
        arr[s.charAt(i)-'a']++;
    }
    PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->(b-a));
    for (int i = 0; i < 26; i++) {
        if(arr[i]>0){
            pq.offer(arr[i]);
        }
    }
    int idx=0;  //[1.9], [10,18]
    while(!pq.isEmpty()){
        int cur=pq.poll();
        idx++;
        if(idx<=9){
            res+=cur;
        }else if(idx<=18){
            res+=cur*2;
        }else{
            res+=cur*3;
        }
    }
    return res;
}

856. Score of Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int scoreOfParentheses(String s) {
    int res=0;
    int depth=0;
    for (int i = 0; i < s.length(); i++) {
        char c=s.charAt(i);
        if(c=='('){
            depth++;
        }else{
            depth--;
        }
        if(c==')' && s.charAt(i-1)=='('){
            res+=Math.pow(2,depth);
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int scoreOfParentheses(String s) {
        int n=s.length();
        int cur=0;
        Deque<Integer> stack=new LinkedList<>();
        //(()())
        for (int i = 0; i < n; i++) {
            char c=s.charAt(i);
            if(c=='('){
                stack.push(cur);
                cur=0;
            }else{
                int val=stack.pop();
                cur=val+Math.max(cur*2,1);
            }
        }
        return cur;
    }

422. Valid Word Square

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
public boolean validWordSquare(List<String> words) {
    int max=0;
    for (String word : words) {
        max=Math.max(max,word.length());
    }
    if(max!=words.size()){
        return false;
    }
    char[][] chars=new char[max][max];
    for (int i = 0; i < max; i++) {
        String word=words.get(i);
        for (int j = 0; j < max; j++) {
            if(j==word.length()){
                break;
            }
            chars[i][j]=word.charAt(j);
        }
    }
    for (int i = 0; i < max; i++) {
        for (int j = i+1; j < max; j++) {
            if(chars[i][j]!=chars[j][i]){
                return false;
            }
        }
    }
    return true;
}

439. Ternary Expression Parser

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String parseTernary(String s) {
    Deque<Character> stack=new LinkedList<>();
    for (int i = s.length()-1; i >= 0; i--) {
        char c=s.charAt(i);
        if(!stack.isEmpty() && stack.peek()=='?'){
            stack.pop();
            char a=stack.pop();
            char b=stack.pop();
            if(c=='T'){
                stack.push(a);
            }else{
                stack.push(b);
            }
        }else if(c!=':'){
            stack.push(c);
        }
    }
    return ""+stack.pop();
}

727. Minimum Window Subsequence

Brute force

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
public String minWindow(String s1, String s2) {
    int n1=s1.length();
    int n2=s2.length();
    char[] arr1 = s1.toCharArray();
    char[] arr2 = s2.toCharArray();
    int min=Integer.MAX_VALUE;
    String res="";
    for (int i = 0; i < n1; i++) {
        if(arr1[i]==arr2[0]){
            int idx=0;
            for (int j = i; j < n1; j++) {
                //[i,j]
                if(arr1[j]==arr2[idx]){
                    idx++;
                }
                if(idx==n2){
                    String sub=s1.substring(i,j+1);
                    if(sub.length()<min){
                        res=sub;
                        min=sub.length();
                    }
                    break;
                }
            }
        }
    }
    return res;
}

DP

Two Pointers

750. Number Of Corner Rectangles

TLE 87/94

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
public int countCornerRectangles(int[][] grid) {
    int row=grid.length;
    int col=grid[0].length;
    Set<String> set=new HashSet<>();
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            //[i,j], [i1,j], [i1,j1], [i,j1]
            if(grid[i][j]==1){
                for (int i1 = i+1; i1 < row; i1++) {
                    if(grid[i1][j]==1){
                        for (int j1 = j+1; j1 < col; j1++) {
                            if(grid[i1][j1]==1 && grid[i][j1]==1){
                                String s=convert(i,j)+convert(i1,j)+convert(i1,j1)+convert(i,j1);
                                if(!set.contains(s)){
                                    set.add(s);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return set.size();
}


String convert(int i, int j){
    return i+","+j+";";
}

count pairs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int countCornerRectangles(int[][] grid) {
    int row=grid.length;
    int col=grid[0].length;
    int res=0;
    Map<Integer,Integer> map=new HashMap<>();
    for (int[] r : grid) {
        for (int i = 0; i < col; i++) {
            if(r[i]==1){
                for (int j = i+1; j < col; j++) {
                    if(r[j]==1){
                        int key=i*200+j;
                        int c=map.getOrDefault(key,0);
                        res+=c;
                        map.put(key,c+1);
                    }
                }
            }
        }
    }
    return res;
}

1055. Shortest Way to Form String

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
public int shortestWay(String source, String target) {
    int res=0;
    char[] arr1 = source.toCharArray();
    char[] arr2 = target.toCharArray();
    int j=0;
    boolean[] chars1=new boolean[26];
    boolean[] chars2=new boolean[26];
    for (char c : arr1) {
        chars1[c-'a']=true;
    }
    for (char c : arr2) {
        chars2[c-'a']=true;
    }
    for (int i = 0; i < 26; i++) {
        if(chars2[i] && !chars1[i]){
            return -1;
        }
    }
    while(true){
        res++;
        for (int i = 0; i < arr1.length; i++) {
            if(arr1[i]==arr2[j]){
                j++;
                if(j==arr2.length){
                    return res;
                }
            }
        }
    }
}

1087. Brace Expansion

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 String[] expand(String s) {
    List<StringBuilder> list=new ArrayList<>();
    list.add(new StringBuilder());
    int n=s.length();
    StringBuilder sb=new StringBuilder();
    for (int i = 0; i < n; i++) {
        char c=s.charAt(i);
        if(c=='{'){
            for (StringBuilder old : list) {
                old.append(sb);
            }
            sb=new StringBuilder();
            List<StringBuilder> next=new ArrayList<>();
            int j=s.indexOf("}",i);
            for(int p=i+1; p<j; p++){
                if(s.charAt(p)==','){
                    continue;
                }
                for (StringBuilder old : list) {
                    StringBuilder neo=new StringBuilder(old);
                    neo.append(s.charAt(p));
                    next.add(neo);
                }
            }
            list=next;
            i=j;
        }else{
            sb.append(c);
        }
    }
    for (StringBuilder old : list) {
        old.append(sb);
    }
    String[] arr=new String[list.size()];
    for (int i = 0; i < list.size(); i++) {
        arr[i]=list.get(i).toString();
    }
    Arrays.sort(arr);
    return arr;
}

1153. String Transforms Into Another String

https://leetcode.com/problems/string-transforms-into-another-string/discuss/355382/JavaC%2B%2BPython-Need-One-Unused-Character

结果中不能26个字母全出现！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean canConvert(String str1, String str2) {
    //abc
    //cba
    if(str1.equals(str2)){
        return true;
    }
    Map<Character,Character> map=new HashMap<>();
    for (int i = 0; i < str1.length(); i++) {
        if(map.getOrDefault(str1.charAt(i),str2.charAt(i))!=str2.charAt(i)){
            return false;
        }
        map.put(str1.charAt(i),str2.charAt(i));
    }
    return new HashSet<Character>(map.values()).size()<26;
}

1216. Valid Palindrome III

常做常新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isValidPalindrome(String s, int k) {
    int n=s.length();
    int[][] dp=new int[n][n];
    //dp[i][j]: longest palindrome subsequence length in [i,j]
    //dp[i][j] = dp[i+1][j-1] + 2, if s[i]=s[j]
    for (int i = n-1; i >= 0; i--) {
        dp[i][i]=1;
        for (int j = i+1; j < n; j++) {
            if(s.charAt(i)==s.charAt(j)){
                dp[i][j]=dp[i+1][j-1]+2;
            }else{
                dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
            }
        }
    }
    return n-dp[0][n-1]<=k;
}

680. Valid Palindrome II

传统dp : Memory Limit Exceeded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean validPalindrome(String s) {
    int n=s.length();
    int[][] dp=new int[n][n];
    for (int i = n-1; i >= 0; i--) {
        dp[i][i]=1;
        for (int j = i+1; j < n; j++) {
            if(s.charAt(i)==s.charAt(j)){
                dp[i][j]=dp[i+1][j-1]+2;
            }else{
                dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
            }
        }
    }
    return dp[0][n-1]>=n-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
25
public boolean validPalindrome(String s) {
    int n=s.length();
    int left=0;
    int right=n-1;
    char[] chars=s.toCharArray();
    while(left<right){
        if(chars[left]!=chars[right]){
            return valid(chars,left,right-1) || valid(chars,left+1,right);
        }
        left++;
        right--;
    }
    return true;
}

boolean valid(char[] chars, int lo, int hi){
    while(lo<hi){
        if(chars[lo]!=chars[hi]){
            return false;
        }
        lo++;
        hi--;
    }
    return true;
}

1328. Break a Palindrome

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public String breakPalindrome(String palindrome) {
    if(palindrome.length()==1){
        return "";
    }
    char[] chars=palindrome.toCharArray();
    for (int i = 0; i < chars.length/2; i++) {
        char c=chars[i];
        if(c!='a'){
            chars[i]='a';
            return new String(chars);
        }
    }
    chars[chars.length-1]='b';
    return new String(chars);
}