第3章 字符串

双指针

剑指offerⅡ14：字符串中的变位词

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        int[] counts = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            counts[s1.charAt(i) - 'a']++;
            counts[s2.charAt(i) - 'a']--;
        }
        if (isAllZero(counts)) {
            return true;
        }
        //i是右边界
        for (int i = s1.length(); i < s2.length(); i++) {
            counts[s2.charAt(i) - 'a']--;
            counts[s2.charAt(i - s1.length()) - 'a']++;
            if (isAllZero(counts)) {
                return true;
            }
        }
        return false;
    }

    private boolean isAllZero(int[] counts) {
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
}

剑指offerⅡ15：字符串中的所有变位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

变位词 指字母相同，但排列不同的字符串。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<Integer>();
        if (s.length() < p.length()) {
            return ans;
        }
        int pLength = p.length();
        int[] counts = new int[26];
        int i;
        for (i = 0; i < p.length(); i++) {
            counts[p.charAt(i) - 'a']++;
            counts[s.charAt(i) - 'a']--;
        }
        if (isAllZero(counts)) {
            ans.add(i - pLength);
        }
        for (i = p.length(); i < s.length(); i++) {
            counts[s.charAt(i) - 'a']--;
            counts[s.charAt(i - pLength) - 'a']++;
            if (isAllZero(counts)) {
                ans.add(i - pLength + 1);
            }
        }
        return ans;
    }

    private boolean isAllZero(int[] counts) {
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
}

剑指offerⅡ16：不含重复字符的最长子字符串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

自己的方法（61%，52%）：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        Set<Character> set = new HashSet<>();
        int left = 0, right = 0;//左闭右闭
        int longestLength = 0;
        for (; right < s.length(); right++) {
            //先把right位置的字符暂且看成已经加入了滑动窗口，不断右移left指针，等到没有与该字符重复时，再加入
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }
            set.add(s.charAt(right));//此时加入
            longestLength = Math.max(longestLength, right - left + 1);
        }
        return longestLength;
    }
}

方法一：需要多次遍历整个哈希表（8%，40%）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        int[] counts = new int[128];
        int left = 0, right = 0;//左闭右闭
        //int left =-1,right=0;//左开右闭
        int longestLength = 0;
        for (; right < s.length(); right++) {
            counts[s.charAt(right)]++;
            while (hasCompeate(counts)) {
                counts[s.charAt(left++)]--;//左闭右闭
                //counts[s.charAt(++left)]--;//左开右闭
            }
            longestLength = Math.max(longestLength, right - left + 1);
        }
        return longestLength;
    }

    private boolean hasCompeate(int[] counts) {
        for (int count : counts) {
            if (count > 1) {
                return true;
            }
        }
        return false;
    }
}

方法二：避免多次遍历整个哈希表（99.81%，81.16%）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        int[] counts = new int[128];
        int left = 0, right = 0;//左闭右闭
        int longestLength = 0;
        int countDup = 0;//counts中出现次数大于1的个数
        for (; right < s.length(); right++) {
            counts[s.charAt(right)]++;
            if (counts[s.charAt(right)] == 2) {
                countDup++;
            }
            while (countDup > 0) {
                //counts[s.charAt(left++)]--;
                //不能这么写，因为要先判断删除的位的次数是否为1，判断之后再left++
                counts[s.charAt(left)]--;
                if (counts[s.charAt(left)] == 1) {
                    countDup--;
                }
                left++;
            }
            longestLength = Math.max(longestLength, right - left + 1);
        }
        return longestLength;
    }
}

剑指offerⅡ17：包含所有字符的最短字符串

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

方法一：左闭右闭

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> charToCount = new HashMap<Character, Integer>();
        for (char ch : t.toCharArray()) {
            charToCount.put(ch, charToCount.getOrDefault(ch, 0) + 1);
        }
        int count = charToCount.size();
        int left = 0, right = -1, minLeft = 0, minRight = 0, minLength = Integer.MAX_VALUE;
        while (right < s.length()) {
            if (count > 0) {
                right++;
                if (right < s.length()) {
                    char rightCh = s.charAt(right);
                    if (charToCount.containsKey(rightCh)) {
                        charToCount.put(rightCh, charToCount.get(rightCh) - 1);
                        if (charToCount.get(rightCh) == 0) {
                            count--;
                        }
                    }
                }
                //不能在这里进行right++,原因在下面解释
            } else {
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    minLeft = left;
                    minRight = right;
                }
                char leftCh = s.charAt(left);
                if (charToCount.containsKey(leftCh)) {
                    charToCount.put(leftCh, charToCount.get(leftCh) + 1);
                    if (charToCount.get(leftCh) == 1) {
                        count++;
                    }
                }
                left++;
            }
        }
        return minLength < Integer.MAX_VALUE ? s.substring(minLeft, minRight + 1) : "";
    }
}

重要的思想：对于左闭右闭而言，right++一定要先执行，如果在最后执行right++，那么会right会指向闭区间右端点的后一位,这样就不是左闭右闭了，所以再执行right-left+1计算时可能会出现错误；若left++先执行，left初始值为-1，若left++后执行，初始值为0，先后执行都无所谓。

一般来说，推荐左闭右开的计算方式，利于编程。

方法二：左闭右开

回文字符串

剑指offerⅡ18：有效的回文

给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。本题中，将空字符串定义为有效的 回文串 。

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            char leftCh = s.charAt(left);
            char rightCh = s.charAt(right);
            if (!Character.isLetterOrDigit(leftCh)) {
                left++;
            } else if (!Character.isLetterOrDigit(rightCh)) {
                right--;
            } else {
                leftCh = Character.toLowerCase(leftCh);
                rightCh = Character.toLowerCase(rightCh);
                if (leftCh != rightCh) {
                    return false;
                }
                left++;
                right--;
            }
        }
        return true;
    }
}

剑指offerⅡ19：最多删除一个字符得到回文

给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。s 由小写英文字母组成

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            left++;
            right--;
        }
        return left == s.length() / 2 || isPalinrome(s, left + 1, right) || isPalinrome(s, left, right - 1);
    }

    private boolean isPalinrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

本题思路：跳出while循环时，有三种情况：

• 此时已经遍历完整个数组，即原数组本身是回文
• 两个字符不同，判断[left+1,right]是否回文
• 两个字符不同，判断[left,right-1]是否回文

剑指offerⅡ20：回文子字符串的个数

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。s 由小写英文字母组成

class Solution {
    public int countSubstrings(String s) {
        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 left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

本题思路：回文有2种情况，[i,i]考虑到奇数情况，[i,i+1]考虑偶数情况。