Madam, I'm Adam.

5. Longest Palindromic Substring

middle-out 由每个字符作为起点，往两边扫。

Palindrome 长度可能是奇数，也可能是偶数。所以指定 seed 往两边扩展的时候要注意先把 start / end 指针推到“不是 seed” 的位置上。

while (start >= 0 && end < s.length())

这步判断如果变成 while (end < s.length() && start >= 0)就会超时。

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 1) return s;
        if (s.length() == 2) {
            if (s.charAt(0) == s.charAt(1)) return s;
            return s.substring(1);
        }

        int maxStart = 0;
        int maxEnd = 0;
        int maxLen = 1;

        for (int i = 0; i < s.length(); ++i) {
            int start = i - 1;
            while (start >= 0 && s.charAt(i) == s.charAt(start)) start--;
            int end = i + 1;
            while (end < s.length() && s.charAt(i) == s.charAt(end)) end++;

            while (start >= 0 && end < s.length()) {
                if (s.charAt(start) == s.charAt(end)) {
                    start--;
                    end++;
                } else break;
            }

            if (end - start - 1 > maxLen) {
                maxLen = end - start - 1;
                maxStart = start + 1;
                maxEnd = end - 1;
            }
        }
        return s.substring(maxStart, maxEnd + 1);
    }
}

125. Valid Palindrome

Trivial problem 稍微烦一点的地方在于我们要忽略字符，并且不区分大小写（原始 String 里有字符也有大小写）

涉及到两个函数。

Character.isLetterOrDigit(char chr)
str.toLowerCase();

另外要注意的就是之前提到的双while循环，外层的判断条件也放到内层，否则容易越界。

准确的说，这道题应该是对冲型双指针题。后面总结到的时候再提一下。

public class Solution {
    public boolean isPalindrome(String s) {
        if (s.length() <= 1) return true;
        s = s.toLowerCase();

        int start = 0;
        int end = s.length() - 1;

        while (start < end) {
            while (start < end && !Character.isLetterOrDigit(s.charAt(start)))
                start++;
            while (start < end && !Character.isLetterOrDigit(s.charAt(end)))
                end--;
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else return false;
        }
        return true;
    }
}

266. Palindrome Permutation

Trivial problem 扫一遍所有字符，如果出现过奇数次数的字符超过一个，就不能构造出 Palindrome 了。考察的就是一个简单的对 Palindrome 结构的理解。

用hashmap当然很简单，没什么可说的，一共就256种字符，用一个数组也可以，当然复杂度应该都是相同的。

public class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s.length() <= 1) return true;

        int[] hash = new int[256];
        for (int i = 0; i < s.length(); i++) {
            int index = (int) s.charAt(i);
            hash[index] ++;
        }

        boolean oneOdd = false;
        for (int i = 0; i < 256; i++) {
            if (hash[i] % 2 == 0) {
                continue;
            } else {
                if (oneOdd) return false;
                oneOdd = true;
            }
        }

        return true;
    }
}

267. Palindrome Permutation II

267紧接266，返回所有的可能palindrome，属于搜索问题。根据 palindrome 结构做 DFS + backtracking

仿照permutation那道题的思路写，解法是对的，就是这个暴力解太慢了。挂在了“aaaaaaaa...”那个testcase上。

public class Solution {
    public List<String> generatePalindromes(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() == 0) return result;

        char[] array = s.toCharArray();
        Arrays.sort(array);
        int[] visited = new int[s.length()];
        dfs(result, new StringBuilder(), visited, array);
        return result;
    }
    private void dfs(List<String> result, StringBuilder sb,
                    int[] visited, char[] array) {
        if (sb.length() == array.length && isValid(sb.toString())) result.add(sb.toString());

        int length = sb.length();

        for (int i = 0; i < array.length; ++i) {
            if (visited[i] == 1 || i != 0 && array[i] == array[i - 1] && visited[i - 1] == 0) continue;

            sb.append(array[i]);
            visited[i] = 1;
            dfs(result, sb, visited, array);
            visited[i] = 0;
            sb.setLength(length);
        }
    }
    private boolean isValid(String s) {
        for (int i = 0; i < s.length(); ++i) {
            int j = s.length() - i - 1;
            if (s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }
}

214. Shortest Palindrome

见KMP算法。

131. Palindrome Partitioning

一个比较简单暴力的搜索办法就是直接 DFS + Backtracking，每一步上需要考虑的字问题数量和当前字符串剩余长度相等。

这个解法速度是很慢的。

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if (s == null || s.length() == 0) return result;

        List<String> list = new ArrayList<>();
        dfs(result, list, 0, s);
        return result;
    }
    private void dfs(List<List<String>> result, List<String> list,
                    int index, String s) {
        if (index == s.length()) {
            result.add(new ArrayList<String>(list));
            return;
        }

        for (int i = index; i < s.length(); ++i) {
            String str = s.substring(index, i + 1);
            if(!isValid(str)) continue;

            list.add(str);
            dfs(result, list, i + 1, s);
            list.remove(list.size() - 1);
        }
    }
    private boolean isValid(String s) {
        for (int i = 0; i < s.length(); ++i) {
            int j = s.length() - i - 1;

            if (s.charAt(i) != s.charAt(j)) return false;
            j++;
        }
        return true;
    }
}

132. Palindrome Partitioning II

求方案个数，典型的DP问题。

Palindrome