String Problems

Made by Mike_Zhang

数据结构与算法题主题：

Valid Palindrome II

LeetCode Problem #680

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 validPalindrome(String s) {
        int size = s.length();
        if (size == 1){
            return true;
        }
        int front = 0;
        int end = size-1;
        while (front < end) {
            if (s.charAt(front) != s.charAt(end)) {
                return isPalindrome(s,front, end-1) || isPalindrome(s,front+1,end);
            }
            front++;
            end--;
        }
        return true;
    
    }
    private boolean isPalindrome(String inStr, int i, int j) {
        while (i<j) {
            if (inStr.charAt(i) != inStr.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

Robot Return to Origin

LeetCode Problem #657

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
class Solution {
    public boolean judgeCircle(String moves) {
        
        // M2
        char[] counter = new char[26];
        for (char c: moves.toCharArray()) {
            counter[c-'A']++;
        }
        return counter['L'-'A']==counter['R'-'A'] && counter['U'-'A']==counter['D'-'A'];
        
        // M1
        // int dX = 0;
        // int dY = 0;
        // for (char c: moves.toCharArray()) {
        //     switch (c) {
        //         case 'R':
        //             dX++;
        //             break;
        //         case 'L':
        //             dX--;
        //             break;
        //         case 'U':
        //             dY++;
        //             break;
        //         case 'D':
        //             dY--;
        //     }
        // }
        // return dX==0 && dY==0;
    }
}

Student Attendance Record I

LeetCode Problem #551

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean checkRecord(String s) {
        int timeA = 0;
        int conTimeL = 0;
        int size = s.length();
        for (int i=0;i<size;i++) {
            char c = s.charAt(i);
            if (c=='A') {
                conTimeL = 0;
                if (++timeA>=2) {return false;}
            }
            else if (c=='L') {
                if (++conTimeL >= 3) {return false;}
            }
            else if (c=='P') {
                conTimeL = 0;
            }
        }
        return true;
    }
}

Detect Capital

LeetCode Problem #520

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean detectCapitalUse(String word) {
        int size = word.length();
        boolean firstCap = false;
        int capNum = 0;
        int lowNum = 0;
        for (int i=0;i<size;i++) {
            char c = word.charAt(i);
            if (i==0 && c >='A' && c <= 'Z') {
                firstCap = true;
                capNum++;
            }
            else if (c >='A' && c <= 'Z') {
                capNum++;
            }
            else if (c >='a' && c <= 'z') {
                lowNum++;
            }
        }
        return (firstCap && lowNum == size-1) || (capNum == size) || (lowNum == size);
    }
}

Repeated Substring Pattern

LeetCode Problem #459

1
2
3
4
5
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return (s+s).substring(1,2*s.length()-1).contains(s);
    }
}

Similar method to Rotate String

Number of Segments in a String

LeetCode Problem #434

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
class Solution {
    public int countSegments(String s) {
        
        // M2: to check the beginning of a segment, 1) space + nonspace, or 2) i=0 + nonspace;
        int out = 0;
        int size = s.length();
        for (int i=0;i<size;i++) {
            if ((i==0 && s.charAt(i) != ' ') || s.charAt(i) != ' ' && s.charAt(i-1) == ' ') {
                out++;
            }
        }
        return out;
        
        
        // M1: two pointer to locate a segment
        // int size = s.length();
        // int slow = 0;
        // int out = 0;
        // for (int i=0;i<size;i++) {
        //     char fastChar = s.charAt(i);
        //     char slowChar = s.charAt(slow);
        //     if (fastChar == ' ') {
        //         slow = i+1;
        //     }
        //     if ((fastChar == ' ' && slowChar != ' ') || i == size-1 && slowChar != ' ') {
        //         out++;
        //     }
        // }
        // return out;
    }
}

Add Strings

LeetCode Problem #415

[Math]

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
class Solution {
    public String addStrings(String num1, String num2) {
        int size1 = num1.length();
        int size2 = num2.length();
        int p1 = size1-1;
        int p2 = size2-1;
        StringBuilder out = new StringBuilder();
        int c = 0;
        while (p1>=0 || p2>=0) {
            int n1 = 0;
            int n2 = 0;
            if (p1>=0) {
                n1 = num1.charAt(p1--)-'0';
            }
            if (p2>=0) {
                n2 = num2.charAt(p2--)-'0';
            }
            int temp = n1+n2+c;
            out.insert(0,String.valueOf(temp%10));
            c = temp>=10? 1:0;
        }
        if (c>0) out.insert(0,String.valueOf(1)); // add the final carry out
        return out.toString();
    }
}

Count Binary Substrings

LeetCode Problem #696

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
class Solution {
    public int countBinarySubstrings(String s) {
        
        // 
        int curr = 1, prev = 0, ans = 0;
        for (int i = 1; i < s.length(); i++)
            if (s.charAt(i) == s.charAt(i-1)) curr++;
            else {
                ans += Math.min(curr, prev);
                prev = curr;
                curr = 1;
            }
        return ans + Math.min(curr, prev);
        
        // TL
//         int size = s.length();
//         int count = 0;
//         for (int i=0;i<size;i++) {
//             int nE = 1;
//             int nD = 0;
//             int fast = i+1;
//             while (fast<size && nE > nD && (size-fast)>=nE) {
//                 if (s.charAt(fast) == s.charAt(i)) {
//                     if (nD>0) {break;}
//                     nE++;
//                 }
//                 else {nD++;}
//                 fast++;
//             }
//             if ((nE>0 || nD>0) && nE == nD) {count++;}
            
//         }
//         return count;
    }
}

2022-10-16

To Lower Case

LeetCode Problem #709

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String toLowerCase(String s) {
        
        // M1
        StringBuilder sb = new StringBuilder();
        for (char c: s.toCharArray()) {
            if (c>='A' && c<='Z') {
                c = (char)(c + 'a' - 'A');
            }
            sb.append(c+"");
        }
        return sb.toString();
        
        // M2
        // return s.toLowerCase();
    }
}

2022-10-17

Jewels and Stones

LeetCode Problem #771

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        
        // M1 HashMap
        HashMap<Character, Integer> hm = new HashMap<>();
        int out = 0;
        for (char c : jewels.toCharArray()) {
            hm.put(c,hm.getOrDefault(c,0)+1);
        }
        for (char s: stones.toCharArray()) {
            if (hm.containsKey(s)) {
                out++;
            }
        }
        return out;
    }
}
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
    
        // M2 indexOf
        int out = 0;
        for (char s: stones.toCharArray()) {
            if (jewels.indexOf(s)!=-1) {out++;}
        }
        return out;
    }
}

2022-10-18

Rotate String

LeetCode Problem #796

1
2
3
4
5
class Solution {
    public boolean rotateString(String s, String goal) {
        return s.length()==goal.length() && (goal+goal).contains(s);
    }
}

Similar method to Repeated Substring Pattern

2022-10-19

Reverse Only Letters

LeetCode Problem #917

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
class Solution {
    public String reverseOnlyLetters(String s) {
        char[] c = s.toCharArray();
        int size = s.length();
        int front = 0;
        int end = size-1;
        while (front<end) {
            if (((c[front]>='A' && c[front]<='Z') || (c[front]>='a' && c[front]<='z')) &&
                ((c[end]>='A' && c[end]<='Z') || (c[end]>='a' && c[end]<='z'))) {
                char temp = c[front];
                c[front] = c[end];
                c[end] = temp;
                front++;
                end--;
            }
            else if (c[front]<'A' || (c[front] > 'Z' && c[front]<'a') || c[front]>'z') {
                front++;
            }
            else if (c[end]<'A' || (c[end] > 'Z' && c[end]<'a') || c[end]>'z') {
                end--;
            }
        }
        return new String(c);
    }
}

2022-10-21

Long Pressed Name

LeetCode Problem #925

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
class Solution {
    public boolean isLongPressedName(String name, String typed) {
        if (name.charAt(0) != typed.charAt(0)) {
            return false;
        }
        
        // Using two pointer to check until one to the end
        int left = 1;
        int right = 1;
        while (left<name.length() && right<typed.length()) {
            if (name.charAt(left) == typed.charAt(right)) {
                left++;
                right++;
            }
            else if (typed.charAt(right) == typed.charAt(right-1)) {
                right++;
            }
            else {
                return false;
            }
        }
        
        // Both to the end: true
        if (left == name.length() && right == typed.length()) {
            return true;
        }
        
        // typed is to the end only: must false, for the rest of char in name have not been checked yet
        else if (left < name.length() && right == typed.length()) {
            return false;
        }
        
        // name is to the end. 
        // Now to check whether the rest of char in typed are the chars as same as the last one
        else if (left == name.length() && right < typed.length()) {
            while (right < typed.length()) {
                if (typed.charAt(right) == typed.charAt(right-1)) {
                    right++;
                }
                else {
                    return false;
                }
            }
        }
        return true;
    }
}

2022-10-22

Find Common Characters

LeetCode Problem #1002

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
class Solution {
    public List<String> commonChars(String[] words) {
        
        int[] prev = count(words[0]);
        
        for (int i=1;i<words.length;i++) {
            prev = intersection(prev,count(words[i]));
        }
        
        List<String> out = new ArrayList<>();
        for (int i =0;i<26;i++) {
            if (prev[i]!=0) {
                char a = 'a';
                a += i;
                String str = String.valueOf(a);
              
                int temp = prev[i];
                while (temp != 0) {
                    out.add(str);
                    temp--;
                }
            }
        }
        return out;
    }

    private int[] intersection(int[] inA, int[] inB) {
        int[] out = new int[26];
        for (int i=0;i<26;i++) {
            out[i] = Math.min(inA[i], inB[i]);
        }
        return out;
    }
    
    
    private int[] count (String inStr) {
        int[] out = new int[26];
        for (char c: inStr.toCharArray()) {
            out[c-'a']++;
        }
        return out;
    }
}

2022-10-23

Remove All Adjacent Duplicates In String

LeetCode Problem #1047

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String removeDuplicates(String s) {

        // Using StringBuilder as Stack
        StringBuilder sb = new StringBuilder();
        int size = 0;
        for (char c: s.toCharArray()) {
            if (size != 0 && c == sb.charAt(size-1)) {
                sb.deleteCharAt(size-1);
                size--;
            }
            else {
                sb.append(c);
                size++;
                
            }
        }
        return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String removeDuplicates(String s) {
        
        // Stack 
        Stack<Character> stack = new Stack<>();
        for (char c: s.toCharArray()) {
            if (!stack.isEmpty() && c == stack.peek()) {
                stack.pop();
            }
            else if (stack.isEmpty() || c != stack.peek()) {
                stack.push(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.insert(0,stack.pop());
        }
        return sb.toString();
    }
}

2022-10-24

Isomorphic Strings

LeetCode Problem #205

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character,Character> ht = new HashMap();
        for (int i=0; i<s.length(); i++) {
            char ss = s.charAt(i);
            char tt = t.charAt(i);
            if (!ht.containsKey(ss)) {
                if (ht.containsValue(tt)) {
                    return false;
                }
                ht.put(ss,tt);
            }
            else if (ht.get(ss) != tt){
                return false;
            }
        }
        return true;
    }
}

2022-11-23

First Unique Character in a String

LeetCode Problem #387

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int firstUniqChar(String s) {
        
        // M3
        int size = s.length();
        if (size == 1) {return 0;}
        
        int[] counter = new int[26];
        
        for (int i=0;i<size;i++) {
            counter[s.charAt(i)-'a']++;
        }
        
        for (int j=0;j<size;j++) {
            if (counter[s.charAt(j)-'a'] == 1) return j;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int firstUniqChar(String s) {        
        // M2
        for (char c: s.toCharArray()) {
            int front = s.indexOf(c);
            int end = s.lastIndexOf(c);
            if (front == end) {
                return front;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int firstUniqChar(String s) {
        // M1
        int size = s.length();
        if (size == 1) {return 0;}
        HashMap<Character, Integer> hm = new HashMap<>();
        for (int i=0;i<size;i++) {
            char temp = s.charAt(i);
            if (hm.containsKey(temp)) {
                int v = hm.get(temp);
                v+=1;
                hm.put(temp,v);
            }
            else {
                hm.put(temp,1);
            }
        }
        for (int j=0;j<size;j++) {
            if (hm.get(s.charAt(j)) == 1) {return j;}
        }
        return -1;
    }
}

2022-11-23

Group Anagrams

LeetCode Problem #49

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 List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hm = new HashMap();
        for (String str: strs) {
            String temp = sortString(str);
            if (hm.containsKey(temp)) {
                List<String> tempL = hm.get(temp);
                tempL.add(str);
                hm.put(temp,tempL);
            }
            else {
                List<String> slist = new ArrayList<>();
                slist.add(str);
                hm.put(temp,slist);
            }
        }
        List<List<String>> out = new ArrayList<>();
        for (List<String> ls:hm.values()) {
            out.add(ls);
        }
        return out;
        
    }
    private String sortString(String inStr) {
        char[] out = inStr.toCharArray();
        Arrays.sort(out);
        return new String(out);
    }
}

2022-11-23

Group Shifted Strings

LeetCode Problem #249

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
class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        HashMap<String, List<String>> hm = new HashMap();
        for (String str: strings) {
            String temp = hash(str);
            if (hm.containsKey(temp)) {
                List<String> tempL = hm.get(temp);
                tempL.add(str);
                hm.put(temp,tempL);
            }
            else {
                List<String> slist = new ArrayList<>();
                slist.add(str);
                hm.put(temp,slist);
            }
        }
        List<List<String>> out = new ArrayList<>();
        for (List<String> ls:hm.values()) {
            out.add(ls);
        }
        return out;
        
    }
    private String hash(String inStr) {
        char[] chars = inStr.toCharArray();
        char[] out = new char[chars.length];
        out[0] = 'a';
        for (int i=1;i<out.length;i++) {
            int temp = chars[i]-chars[0];
            out[i] = (char)((temp+26)%26+97);
        }
        return new String(out);
    }
}

2022-11-24

Longest Substring Without Repeating Characters

LeetCode Problem #3

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        // M1
        int size = s.length();
        int fast = 0;
        int slow = 0;
        int max = 0;
        Set<Character> hs = new HashSet<>();
        while (fast<size) {
            char c = s.charAt(fast);
            if (hs.contains(c)) {
                hs.clear();
                slow++;
                fast=slow;
            }
            else {
                hs.add(c);
                max = Math.max(max,hs.size());
                fast++;
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLongestSubstring(String s) {

        // M2
        final int n = s.length();
        int len = 0;
        int [] repeat = new int[128];
        for (int c = 0, j = 0, i = 0; j < n; j++) {
            c = s.charAt(j);
            i = Math.max(repeat[c], i);
            len = Math.max(len, j - i +1);
            repeat[c] = j+1;
        }
        return len;
    }
}

2022-11-25

Last updated on 2022-11-25

References

String - LeetCode

写在最后

String相关的知识会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！

原创文章，转载请标明出处
Made by Mike_Zhang




感谢你的支持
Data Structure and Algorithm > Problem Set
#Java #String
String Problems
https://ultrafish.io/post/string-problems/
Author
Mike_Zhang
Posted on
November 25, 2022
Licensed under