算法：（三）字符串

3.1 双指针

面试题14：字符串中的变位词

题目：输入字符串s1和s2，如何判断字符串s2中是否包含字符串s1的某个变位词？如果字符串s2中包含字符串s1的的某个变位词，则s1至少有一个变位词是s2的子字符串。假设两个字符串中只包含英文小写字母。例如，字符串s1为"ac"，字符串s2为"dgcfa"，由于字符串s2包含s1的变位词"ca"，因此输出为true。如果字符串s1为"ab"，字符串s2为"dgcaf"，则输出为false。

思路：hash表+双指针

public boolean checkInclusion(String s1, String s2){
    /**
     * 双指针+hash表（用数组做hash表）
     * 先将s1的字符信息存入hash表，
     * hash表的键是字符（这里用数组下标表示各个字符，例如下标0表示字符'a'，下标1表示字符'b'），hash表的值为字符出现的次数
     * 然后遍历s2，利用双指针同时位移，移进的字符，hash表对应的值就减1，移出的字符，hash表对应的值就加1
     * 每次位移都判断hash表是否全为0（这个操作时间复杂度为O(1),每次执行固定26步操作）
     * 直至双指针位移结束
     * 时间复杂度O(n)
     */
    if(s2.length() < s1.length()){
        return false;
    }
    int[] hash = new int[26];
    for (int i = 0; i < s1.length(); i++) {
        // 在将s1信息存入hash中时，已经开始对s2的遍历的初始化
        hash[s1.charAt(i) - 'a']++;
        hash[s2.charAt(i) - 'a']--;
    }
    if (ifAllZero(hash)){
        return true;
    }
    for (int right = s1.length(); right < s2.length(); right++){
        hash[s2.charAt(right) - 'a']--;
        hash[s2.charAt(right - s1.length())]++;
        if (ifAllZero(hash)){
            return true;
        }
    }
    return false;
}

public boolean ifAllZero(int[] array){
    for (int i : array) {
        if (i != 0){
            return false;
        }
    }
    return true;
}
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

面试题15：字符串中所有的变位词

题目：输入字符串s1和s2，如何找出字符串s2中所有的变位词在字符串s1中的起始下标？假设两个字符串中只包含英文小写字母。例如：字符串s1为"cbadabacg"，字符串s2为"abc"，字符串s2的两个变位词"cba"和"bac"是字符串s1中的子字符串，输出他们在字符串s1中的起始下标0和5。

思路：hash表+双指针，14题的变种

public List<Integer> checkInclusion(String s1, String s2){
    /**
     * 和14题基本一摸一样，只是返回值不一样，返回的是变位词其实下标，得right - s2.length() + 1
     */
    List<Integer> result = new LinkedList<>();
    if(s1.length() < s2.length()){
        return result;
    }

    int[] hash = new int[26];
    for (int i = 0; i < s2.length(); i++) {
        // 在将s1信息存入hash中时，已经开始对s2的遍历的初始化
        hash[s2.charAt(i) - 'a']++;
        hash[s1.charAt(i) - 'a']--;
    }
    if (ifAllZero(hash)){
        result.add(0);
    }
    for (int right = s2.length(); right < s1.length(); right++){
        hash[s1.charAt(right) - 'a']--;
        hash[s1.charAt(right - s2.length())]++;
        if (ifAllZero(hash)){
            result.add(right - s2.length() + 1);
        }
    }
    return result;
}
public boolean ifAllZero(int[] array){
    for (int i : array) {
        if (i != 0){
            return false;
        }
    }
    return true;
}
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

面试题16：不包含重复字符的最长子字符串

题目：输入一个字符串，求改字符串中不含重复字符的最长子字符串的长度。例如，输入字符串"babcca"，其最长不含重复字符的子字符串"abc"，长度为3。

思路：hash表+双指针

public int lengthOfLongestSubstring(String s){
        /**
         * 用双指针left和right来确定一个子字符串，用hash表记录该子字符串中所有字符出现的次数
         * 如果hash表中所有字符出现的次数不超过1，则说明该子字符串是不重复的，于是移动right指针，尝试向子字符串中添加新的字符
         * 添加新的字符后要判断hash表中所有字符出现的次数是否依然不超过1，若不超过1则更新最长子串长度，继续右移right
         * 若hash表中所有字符出现的次数是否依然超过1，则要移动left指针，从子串中删除字符，直至hash表中所有字符出现自述都不超过1
         * 如此循坏直至right指针遍历至字符串s最右端
         * 时间复杂度O(n)
         */
        if(s.length() < 1){
            return 0;
        }
        // ascii字符集
        int[] hash = new int[256];
        int right = 0;
        int left = -1;
        int longest = 0;
        while(right < s.length()){
            hash[s.charAt(right)]++;
            while (hasGreaterThan1(hash)){
                hash[s.charAt(++left)]--;
            }
            longest = Math.max(right - left, longest);
            right++;
        }
        return longest;
    }
    public boolean hasGreaterThan1(int[] array){
        for (int i : array) {
            if (i > 1){
                return true;
            }
        }
        return false;
    }
    public int lengthOfLongestSubstringPro(String s){
        /**
         * 上面的方法每次都要遍历hash数组，需要执行256步遍历
         * 虽然时间复杂度量级上还是O(1)，但实际上非常耗时
         * 故优化算法，使用一个变量countDup来记录hash表中是否有字符出现次数超过1，每次字符移进和移除都要维护countDup
         */
        if(s.length() == 0){
            return 0;
        }
        // ascii字符集
        int[] hash = new int[256];
        int right = 0;
        int left = -1;
        int longest = 0;
        int countDup = 0;
        while(right < s.length()){
            hash[s.charAt(right)]++;
            if(hash[s.charAt(right)] == 2){
                countDup++;
            }
            while (countDup > 0){
                hash[s.charAt(++left)]--;
                if(hash[s.charAt(left)] == 1){
                    countDup--;
                }
            }
            longest = Math.max(right - left, longest);
            right++;
        }
        return longest;
    }
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

面试题17：包含所有字符的最短字符串

题目：输入两个字符串s和t，请找出字符串s中包含到的字符串t的所有字符的最短子字符串。例如，输入的字符串s为"ADDBANCAD"，字符串t为"ABC"，则字符串s中包含字符‘“A”、“B”、“C"的最短子字符串是"BANC”。如果不存在符合条件的子字符串，则返回空字符串""。如果存在多个符合条件的子字符串，则返回任意一个。

思路：hash表+双指针

public String minWindow(String s, String t){
    /**
     * 还是用hash表+双指针
     * hash用于存放t的所有字符，双指针用来从s中寻找子字符串、
     * 时间复杂度为O(n)，空间复杂度为O(n)
     */
    HashMap<Character,Integer> hash = new HashMap<>();
    for (char c : t.toCharArray()) {
        // 统计t中所有出现的字符及其出现的次数
        hash.put(c, hash.getOrDefault(c, 0) + 1);
    }
    int minLength = Integer.MAX_VALUE;
    // count代表还未出现在s的子字符串中的t的字符，用于简化hash表的遍历
    int count = hash.size();
    // 双指针索引
    int start = 0, end = 0;
    // 记录最短字符串出现的位置
    int minStart = 0, minEnd = 0;
    while(end < s.length() || (count == 0 && end == s.length())){
        if(count > 0){
            char endChar = s.charAt(end);
            if(hash.containsKey(endChar)){
                hash.put(endChar, hash.get(endChar) - 1);
                if(hash.get(endChar) == 0){
                    count--;
                }
            }
            // end永远指向当前判断字符的下一个未判断的字符
            end++;
        } else {
            // 当count为0时，更新最短长度的值
            if(end - start < minLength){
                minLength = end - start;
                // 其实minEnd应该是end - 1，但String.substring()是左闭右开。怎么写都可以
                minEnd = end;
                minStart = start;
            }

            char startChar = s.charAt(start);
            if(hash.containsKey(startChar)){
                hash.put(startChar, hash.get(startChar) + 1);
                if (hash.get(startChar) == 1){
                    count++;
                }
            }
            start++;
        }
    }
    return minLength == Integer.MAX_VALUE ? s.substring(minStart, minEnd) : "";
}
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

3.2 回文字符串

面试题18：有效的回文

题目：给定一个字符串，请判断它是不是回文。假设只需要考虑字母和数字字符，并忽略大小写。例如，"Was it a cat I saw?"是一个回文字符串，而"race a car"不是回文字符串。

思路：头尾双指针

public boolean isPalindrome(String str){
    int i = 0;
    int j = str.length() - 1;
    while(i < j){
        // 过滤非字母字符
        if(Character.isLetterOrDigit(str.charAt(i))) {
            i++;
        } else if(Character.isLetterOrDigit(str.charAt(j))) {
            j--;
        } else {
            // 忽略大小写
            char c1 = Character.toLowerCase(str.charAt(i));
            char c2 = Character.toLowerCase(str.charAt(j));
            if(c1 != c2){
                return false;
            }
            i++;
            j--;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

面试题19：最多删除一个字符得到回文

题目：给定一个字符串，请判断如果最多从字符串中删除一个字符能否得到一个回文字符串。例如，如果输入字符串"abca"，由于删除字符’b’或’c’就能得到一个回文字符串，因此输出true。

思路：头尾双指针

public boolean validPalindrome(String str){
    int start = 0;
    int end = str.length() - 1;
    while(start < str.length() / 2){
        if(str.charAt(start++) != str.charAt(end--)){
            break;
        }
    }
    // 本身是否是回文 || 删除左边一个字符是否时候回文 || 删除右边一个字符是否是回文
    return start == str.length() / 2 || isPalindrome(str, start++, end) || isPalindrome(str, start, end--);
}

public boolean isPalindrome(String str, int start, int end){
    /**
     * 判断一个字符串的某个位置是否是回文字符串
     */
    while(start < end){
        if(str.charAt(start++) != str.charAt(end--)){
            return false;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

面试题20：回文子字符串的个数

题目：给定一个字符串，请问该字符串中有多少个回文连续子字符串？例如，字符串"abc"有三个回文子字符串，分别是"a"、“b"和"c”，“aaa"有6个回文子字符串，分别为"a”、“a”、“a”、“aa”、“aa"和"aaa”。

思路：中心双指针

public int countSubstring(String s){
	/**
     * 遍历字符串每个字符，判断从当前字符开始可以生成多少个回文字符串
     * 当前字符可以生成两种回文字符串：奇数回文和偶数回文
     */
    if(s == null || s.length() < 1){
        return 0;
    }
    int count = 0;
    for(int i = 0; i < s.length(); i++){
        // 奇数回文子字符串
        count += countPalindrome(s, i, i);
        // 偶数回文子字符串
        count += countPalindrome(s, i, i + 1);
    }
    return count;
}

private int countPalindrome(String s, int start, int end) {
    /**
     * 一个字符串从某个位置开始能产生的回文子字符串的个数
     */
    int count = 0;
    while(start >=0 && end < s.length() && s.charAt(start) == s.charAt(end)){
        count++;
        start--;
        end++;
    }
    return count;
}
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