【剑指offer2】 chap3 字符串

• Character

  • Java Character 类 | 菜鸟教程

Character.isLetterOrDigit(ch1)
Character.toLowerCase(ch1)

• String

• Java StringBuffer 和 StringBuilder 类

        Java StringBuffer 和 StringBuilder 类 | 菜鸟教程

StringBuffer str; 
str.toString(); 
str.append(char ch);

• 滑动窗口+哈希表【小写字母26个，ASCII码256个，可以用数组记录】

  • 剑指 Offer II 014. 字符串中的变位词

  • 剑指 Offer II 015. 字符串中的所有变位词

  • 剑指 Offer II 016. 不含重复字符的最长子字符串

  • 剑指 Offer II 017. 含有所有字符的最短字符串

• 剑指 Offer II 018. 有效的回文

• 剑指 Offer II 019. 最多删除一个字符得到回文

public boolean validPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j && s.charAt(i) == s.charAt(j)) {
        i++;
        j--;
    }
    return i == s.length() / 2 + 1 || isPalindrome(s,i,j-1) || isPalindrome(s,i+1,j);
}

private static boolean isPalindrome(String s, int start, int end) {
    while (start < end) {
        if (s.charAt(start) != s.charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

• 剑指 Offer II 020. 回文子字符串的个数

  • 双指针

  • 马拉车算法

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 start, int end) {
    int count = 0;
    int i = start, j = end;
    while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
        count++;
        i--;
        j++;
    }
    return count;
}