A typical way to solve *palindrome* problems


  • 1
    F

    Here's a typical way to solve palindrome problems using DP.
    For palindrome sequence, there are two sub problems(palindrome with even length and palindrome with odd length).
    How to solve palindrome problems according to these two categories makes me crazy for a long time.

    Then I come up with a typical solution after reading several solutions for each palindrome problems. Hope it helps!

    1. We first define a 2D array.
    2. Initialize dp[i][i] according to each problems.
    3. Initialize dp[i][i+1].
    4. To find dp[i][j] iteratively, we start from gap = 2 (which means the length of current subsequence is 3).

    For example, for sequence "aaa",
    gap = 2, i = 0, then j = i + gap = 2.
    s.charAt(i) == s.charAt(j),
    then, dp[i][j] = dp[i + 1][j - 1] + 2 = dp[1][1] + 2 = 3.

    Thus, the relation function can be reached by

    for (int gap = 2; gap < s.length(); gap++) {
         for (int i = 0; i < s.length() - gap; i++) {
                int j = i + gap;
                if (s.charAt(i) == s.charAt(j)) {
                    / ***** / 
                } else {
                    / ***** /
                }
         }
    }
    

    Longest Palindromic Subsequence

        public int longestPalindromeSubseq(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            int[][] f = new int[s.length()][s.length()];
            for (int i = 0; i < s.length(); i++) {
                f[i][i] = 1;
            }
            for (int i = 0; i < s.length() - 1; i++) {
                if (s.charAt(i) == s.charAt(i + 1)) {
                    f[i][i + 1] = 2;
                } else {
                    f[i][i + 1] = 1;
                }
            }
            for (int gap = 2; gap < s.length(); gap++) {
                for (int i = 0; i < s.length() - gap; i++) {
                    int j = i + gap;
                    if (s.charAt(i) == s.charAt(j)) {
                        f[i][j] = f[i + 1][j - 1] + 2;
                    } else {
                        f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                    }
                }
            }
            return f[0][s.length() - 1];
        }
    

    Number of Palindrome Substring
    Given "aaa"
    return 6
    ("a" "a" "a" "aa" "aa" "aaa") There are 6 Palindromic substrings.

    	public static int countPalindromSubstring(String s) {
    		if(s == null || s.length() == 0) {
    			return 0;
    		}
    		int n = s.length();
    		int count = 0;
    		boolean[][] f = new boolean[n][n];
    		for(int i = 0; i < n; i++) {
    			f[i][i] = true;
    			count++; 
    		}
    		for(int i = 0; i < n - 1; i++) {
    			if(s.charAt(i) == s.charAt(i + 1)) {
    				f[i][i + 1] = true;
    				count++;
    			}
    		}
    		for(int gap = 2; gap < n; gap++) {
    			for(int i = 0; i < n - gap; i++) {
    				int j = i + gap;
    				if(s.charAt(i) == s.charAt(j)) {
    					if(f[i + 1][j - 1]) {
    						f[i][j] = true;
    						count++;
    					}
    				}
    			}
    		}
    		return count;
    	}
    

  • 0
    A

    nice solution!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.