leetcode 647. Palindromic Substrings

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:

1. The input string length won't exceed 1000.

這道題用DP的話蠻容易的，思路比較好想。DP[ i ][ j ] 存儲 index 從 i ~ j 是不是回文。

public int countSubstrings(String s) {
	if(s.equals("")){
		return 0;
	}
	int count=0;
	char[] cs=s.toCharArray();
	int n=cs.length;
	boolean DP[][]=new boolean[n][n];
	for(int i=0;i<n;i++){
		DP[i][i]=true;
	}
	count+=n;
	for(int len=1;len<n;len++){
		for(int i=0;i<n-len;i++){
			int j=i+len;
			if(cs[i]!=cs[j]){
				DP[i][j]=false;
			}
			else{
				DP[i][j]=ifHuiWen(DP, i+1, j-1);
				if(DP[i][j]==true){
					count++;
				}
			}
		}
	}
	return count;
}

public boolean ifHuiWen(boolean DP[][],int i,int j){
	if(i>=j){
		return true;
	}
	else{
		return DP[i][j];
	}
}
           

大神想到了一個不用DP的方法：

思路是 考慮不同的回文中心，然後從中心擴大，求以某個中心來獲得的回文個數。

有兩種情況：子串 s[ i - j , ...,  i + j ] 中, i 是回文中心（這是奇數串的情形）。子串 s[ i - 1 - j , ...,  i + j ] 中，( i - 1 , i ) 是回文中心（這是偶數串的情形）。

public int countSubstrings(String s) {
    int res = 0, n = s.length();
    for(int i = 0; i<n ;i++ ){
        for(int j = 0; i-j >= 0 && i+j < n && s.charAt(i-j) == s.charAt(i+j); j++){
        	res++; //substring s[i-j, ..., i+j]
        }
        for(int j = 0; i-1-j >= 0 && i+j < n && s.charAt(i-1-j) == s.charAt(i+j); j++){
        	res++; //substring s[i-1-j, ..., i+j]
        }
    }
    return res;
}