PalindromicSubstrings [source code]

public class PalindromicSubstrings {
static
/******************************************************************************/
public class Solution {
    public int countSubstrings(String s) {
        if (s.length() <= 1)
            return s.length();
        char[] chs = s.toCharArray();
        int sum = 0;
        for (int i = 0; i < chs.length; i++) {
            sum += extendPalindrome(chs, i, i) + extendPalindrome(chs, i, i + 1);
        }
        return sum;
    }

    public int extendPalindrome(char[] chs, int left, int right) {
        int offset = left == right ? 1 : 0;
        while (left >= 0 && right < chs.length && chs[left] == chs[right]) {
            left--;
            right++;
        }
        int length = right - left + 1 - 2;
        return length / 2 + offset;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PalindromicSubstrings.Solution tester = new PalindromicSubstrings.Solution();
        String[] inputs = {
            "abc", "3",
            "aaa", "6", 
            "abcba", "7",
            "abccba", "9",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            String s = inputs[2 * i];
            int expected = Integer.parseInt(inputs[1 + 2 * i]);
            System.out.println(Printer.seperator());
            int output = tester.countSubstrings(s);
            System.out.println(Printer.wrapColor(s, "magenta") + " -> " + output + Printer.wrapColor(", expected: " + expected, output == expected ? "green" : "red"));
        }
    }
}

这题居然连个笨办法都想不出来. 刚开始想要用sliding window来做, 但是好像palindrome问题用sliding window不是特别灵光? 感觉sliding window处理的更多是基于frequency/counts这种信息的substring问题, palindrome这个光是有counts类的信息是不够的, 你还需要知道这个occurrence对应的位置的信息;

发现一个思路不对就要想其他的思路, 面试的时候要一边这样想一边说出来, 如果这个放弃的决定有问题, 一般的面试官估计还是会提醒一下的;

很多时候拿到一个题目想要DP做到时候, 题目还没有读透就开始找DP value是很困难的. 一般要稍微理解一下这个问题的本质, 比如想一个笨办法, 知道一般的找我们最终的这个target value的思路是什么, 然后在这个思路的过程中看看有没有什么consituent value是有DP Property的;

大概想到一点思路, 就是首先我们还是要找一个DP value, 这里这个DP value应该跟root, 也就是nth entry有关系的. 我的想法是OPT(N)可以由两部分组成, 一个是单个字母的, 这个等于是在OPT(N-1)对应这部分的基础上+1. 另一部分是考虑[n-1]是否被include在一个palindrome里面, 如果是, 那么也有一个可以增加的计算量: 比如bcdcb除开单字母带来的贡献是5 / 2, 而abcdcba带来的贡献是7 / 2. 所以问题就在于怎么向左找到longest palindrome substring that contains [n-1].

discussion瞄了一眼好像相对比较差的都是N^2的时间, 所以我们这个find longest palindrome的过程至多只能有O(N)的时间, 这个想不到怎么做了;

最后这个问题是完全没有想出来怎么写, 上面的代码是discussion上面看来的, 速度是11ms (100%):

public class Solution {  
    int count = 0;  

    public int countSubstrings(String s) {  
        if (s == null || s.length() == 0) return 0;  

        for (int i = 0; i < s.length(); i++) { // i is the mid point  
            extendPalindrome(s, i, i); // odd length;  
            extendPalindrome(s, i, i + 1); // even length  
        }  

        return count;  
    }  

    private void extendPalindrome(String s, int left, int right) {  
        while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)) {  
            count++; left--; right++;  
        }  
    }  
}

这个是人家自己的原来的代码. 跟我的写法有一点区别, 不过主体的思路是一样的. 写完之后我发现他这个一个全局count的好像更新起来比我的方便. 我这个要考虑怎么处理单字母的情况. 他这个只有在[left] == [right]的时候count++的思路, 其实也包含了我这个offset的处理思路: extend(i,i)才有可能一开始就有一个++, extend(i, i+1)的call只有从第二个iteration开始才会有++;

这里是discussion另外一个版本, 不使用global, 不过计算count的时候还是用increment的方式, 而不是我的直接端点计算的方式:

public int countSubstrings(String s) {  
    char[] ss = s.toCharArray();  
    int count = 0;  
    for (int i = 0; i < s.length(); i++) {  
        count += count(ss, i, i);  
        count += count(ss, i, i + 1);  
    }  
    return count;  
}  

int count(char[] s, int l, int h) {  
    int count = 0;  
    for (; l >=0 && h < s.length && s[l] == s[h]; l--, h++, count++);  
    return count;  
}

所以这个题目还是反映了一个前面的结论: 当我陷入一个套路没有办法做出来的时候, 往往这个题目有一个关键的intuition我没有发现;

这个题目是palindrome问题. 跟在Manacher算法当中类似, palindrome算法问题, 貌似从center开始处理的思路比较多也比较好; 这样一个intuition可以让问题简化很多;

更广义的来说, 这个问题的失利, 让我想到一个另外的问题: where to start your iteration? 以前很少想这个问题. 当然, 站在计算机的角度来讲, 肯定计算机本身能够iterate的只有一个sequence. 关键是什么样的一个sequence.

不能因为你最后要寻找的比如是这样也一个substring, 所以你就整个substring都iterate一边, from one end to another. 对称性的存在, 意味着从center iterate更加有利;

当然还有更加复杂的iterate方式, 比如有规律的跳子, 以及无规律的跳子(通过一个formula来更新iteration var), 等等, 这些暂时都是无法总结的, 不过脑子里要把这个空档打开, 知道有这么一个选择的空间(latitude)存在;

这个算法的时间是O(N^2), 更具体的来说是, (N^2) / 4: WorstCase是全都是相同的, 然后你自己大概算一下就知道了;

上面这个算法是O(N^2)的. discussion上面有人提出这个问题是可以直接用Manacher来做的, 做到O(N). 而且他给出了代码, 不过是Python的所以我暂时也看不懂;

好像目前为止discussion上面的解都是这样的直接做出来的解, 并没有看到DP的解法;

看到一个:

public class Solution {  
    public int countSubstrings(String s) {  

        int sLen = s.length();  
        char[] cArr = s.toCharArray();  

        int totalPallindromes = 0;  

        boolean[][] dp = new boolean[sLen][sLen];  

        // Single length pallindroms  
        for (int i = 0; i < sLen; i++) {  
            dp[i][i] = true;  
            totalPallindromes++;  
        }  

        // 2 length pallindromes  
        for (int i = 0; i < sLen - 1; i++) {  
            if (cArr[i] == cArr[i + 1]) {  
                dp[i][i + 1] = true;  
                totalPallindromes++;  
            }  
        }  

        // Lengths > 3          
        for (int subDistance = 2; subDistance < sLen; subDistance++) {  

            for (int i = 0; i < sLen - subDistance; i++) {  

                int j = i + subDistance;  

                if (dp[i + 1][j - 1] && cArr[i] == cArr[j]) {  
                    dp[i][j] = true;  
                    totalPallindromes++;  
                }  
            }  
        }          
        return totalPallindromes;  

    }  
}

这个DP的思路也是符合我之前对于DP问题的总结, 这里他的DP表格记录的DP value是whether substring[i..j] is a palindrome. 这样设置的一个value是有DP Property的; 而且这个DP value可以作为跳板来求出我们的target value. 这个就是我们之前一直总结的DP思路的两条黄金要求;

当然总结起来很简单, 真正想到做这个DP value也并不是那么简单的;

另外注意他这里的循环方式, 在Bottom-Up更新这个表格的时候, 注意看他是怎么写这个循环的变量的: 最外层的循环控制length, 然后内层的循环同时产生两个index. 这个跟一般以前常见的DP表格的更新方式还是有一点区别的. 不过其实本质上的变化并没有, 因为你最后想要做到的内容其实就是sweep整个表格, 至于用什么样的方式的顺序来做, 就看你自己的选择. 如果用平面几何的观点来看, 他这里就是按照y - x = k的k的取值, 一条线一条线的来sweep的; 只能说这种sweeping本身并没有固定要求必须要的方式, 还是要看问题的取舍;

这个问题之所以要按照length的顺序, 是因为palindrome问题就是这样的, 你想要知道[i][j]是否是TRUE, 你就要先知道[i+1][j-1]. 有没有注意一个问题, 包括这里的这个表格的更新方式, 或者是之前BetterDiff的时候的那个DP的更新方式, 虽然说我们明确的说表格要有两个index什么的怎么样怎么样, 但是实际上, 真正在解决问题的时候, 你还是要把index实际代表的是什么代入到实际的问题当中, 才能知道怎么做DP value的更新; 比如这里, 你要站在一个string的角度, 想想i和j两个指针的移动: 这里事实上连第一个iteration var, 也就是subDistance, 都没有出现; 在BetterDiff的时候也是, 要把两个string的index理解为index所在位置实际的character;

感觉理论上来说, 好像直接用i,j两个指针来做两层sweeping循环的var也可以; 不过这里用subDistance来做更好: 从subLen短的开始, 到长的, 这样当你比如到了一个iteration, 需要考虑一个subLen是4的情形是否是TRUE的时候, 你已经对所有subLen是2的结果都有了, 这个就达到了一个正确的Bottom-Up的顺序: 这个问题463上课的时候也说过, Bottom-Up的时候一个重要问题就是这个sweep的顺序的选择: 要保证当up的位置想要一个entry的value的时候, 这个entry肯定已经被填上了;

还有一个没看懂的DP答案: https://discuss.leetcode.com/topic/96932/c-clear-dp-solution

    int countSubstrings(string s) {  
        if(s.size()==0) return 0;  
        int res=0;  
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));  
        dp[0][0]=2;  
        for(int i=1;i<s.size();i++) {  
            for(int j=0;j<i;j++) {  
                if(dp[i-1][j]==2&&s[i]==s[i-1]) dp[i][j+1]=2;  
                else if(dp[i-1][j]>0&&j!=i-1&&s[i-j-2]==s[i]) dp[i][j+2]=1;  
            }  
            dp[i][0]=2;  
        }  
        for(int i=0;i<dp.size();i++) {  
            for(int j=0;j<dp[i].size();j++) res+=min(1, dp[i][j]);  
        }   
        return res;  
    }

Problem Description

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
The input string length won't exceed 1000.
Difficulty:Medium
Total Accepted:1.7K
Total Submissions:2.9K
Contributor: Stomach_ache
Companies
linkedin
Related Topics
dynamic programming string
Similar Questions
Longest Palindromic Substring Longest Palindromic Subsequence Palindromic Substrings

Problem Description

这个是Sedgwick的Manacher的代码, 正好贴在这里算了:

public class Manacher {  
    private int[]  p;  // p[i] = length of longest palindromic substring of t, centered at i  
    private String s;  // original string  
    private char[] t;  // transformed string  

    public Manacher(String s) {  
        this.s = s;  
        preprocess();  
        p = new int[t.length];  

        int center = 0, right = 0;  
        for (int i = 1; i < t.length-1; i++) {  
            int mirror = 2*center - i;  

            if (right > i)  
                p[i] = Math.min(right - i, p[mirror]);  

            // attempt to expand palindrome centered at i  
            while (t[i + (1 + p[i])] == t[i - (1 + p[i])])  
                p[i]++;  

            // if palindrome centered at i expands past right,  
            // adjust center based on expanded palindrome.  
            if (i + p[i] > right) {  
                center = i;  
                right = i + p[i];  
            }  
        }  

    }  

    // Transform s into t.  
    // For example, if s = "abba", then t = "$#a#b#b#a#@"  
    // the # are interleaved to avoid even/odd-length palindromes uniformly  
    // $ and @ are prepended and appended to each end to avoid bounds checking  
    private void preprocess() {  
        t = new char[s.length()*2 + 3];  
        t[0] = '$';  
        t[s.length()*2 + 2] = '@';  
        for (int i = 0; i < s.length(); i++) {  
            t[2*i + 1] = '#';  
            t[2*i + 2] = s.charAt(i);  
        }  
        t[s.length()*2 + 1] = '#';  
    }  

    // longest palindromic substring  
    public String longestPalindromicSubstring() {  
        int length = 0;   // length of longest palindromic substring  
        int center = 0;   // center of longest palindromic substring  
        for (int i = 1; i < p.length-1; i++) {  
            if (p[i] > length) {  
                length = p[i];  
                center = i;  
            }  
        }  
        return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2);  
    }  

    // longest palindromic substring centered at index i/2  
    public String longestPalindromicSubstring(int i) {  
        int length = p[i + 2];  
        int center = i + 2;  
        return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2);  
    }  



    // test client  
    public static void main(String[] args) {  
        String s = args[0];  
        Manacher manacher = new Manacher(s);  
        StdOut.println(manacher.longestPalindromicSubstring());  
        for (int i = 0; i < 2*s.length(); i++)  
            StdOut.println(i +  ": " + manacher.longestPalindromicSubstring(i));  

    }  
}