深究 - 回文

  • 时间:
  • 浏览:
  • 来源:互联网

相关回文问题 (Java)

回文(Palindrome)

  • aba
  • abba 
  • 上海自来水来自海上
  • 天上飞机飞上天

有效回文串(Valid Palindrome) 

Java字符类的几个常用函数
- isLetter(c)

- isDigit(c)

- toLowerCase(c)

- toUpperCase(c)

//Validate if the character is the letter or digit
public boolean isValid(char c) {
        return Character.isLetter(c) || Character.isDigit(c);
}

//Validate if the two data equal
public boolean isEquals(String s, int left, int right) {
        return s.toLowerCase().charAt(left) == s.toLowerCase().charAt(right);
}

public boolean isPalindrome(String s) {
    if (s == null) {
        return true;
    }

    int left = 0, right = s.length() - 1;
    while (left < right) {
        while (left < right && !isValid(s.charAt(left))) {
                left++;
        }
        while (left < right && !isValid(s.charAt(right))) {
            right--;
        }

        if (left < right && !isEquals(s, left, right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
        
}

最长回文序列(Longest Subsequence)

子序列(Subsequence):非连续字符 

数量级: O(2^n),每个字符都有选或不选两种可能

例:abcd

a b c d / ab ac ad bc bd cd / abc abd acd bcd / abcd

思路 动态规划

对于任意字符串

如果首尾字符相同,那么字符串的最长子序列 = 去掉首尾的字符串的最长子序列 + 首尾

如果首尾字符不同,则最长子序列 = 较大者:去掉首的字符串的最长子序列,去掉尾的字符串的最长子序列

dp[i][j] = dp [i + 1][j - 1] + 2                          if (str[i] == str[j])

dp[i][j] = max(dp [i + 1][j], dp [i][j - 1])          if (str[i] != str[j])

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

递归方法 

public class Solution {
    int[][] f = null;
    char[] s = null;
    int res = 0;

    private void Compute(int i, int j) {
        if (f[i][j] != -1) {
            return;
        }

        if (i == j) {
            f[i][j] = 1;
            return;
        }

        if (i + 1 == j) {
            if (s[i] == s[j]) {
                f[i][j] = 2;
            }
            else {
                f[i][j] = 1;
            }

            return;
        }

        Compute(i + 1, j);
        Compute(i, j - 1);
        Compute(i + 1, j - 1);
        f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
        if (s[i] == s[j]) {
            f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
        }
    }

    public int longestPalindromeSubseq(String ss) {
        s = ss.toCharArray();
        int n = s.length;
        if (n == 0) {
            return 0;
        }
        
        if (n == 1) {
            return 1;
        }
        
        int i, j;
        f = new int[n][n];    
        for (i = 0; i < n; ++i) {
            for (j = i; j < n; ++j) {
                f[i][j] = -1;
            }
        }
        
        Compute(0, n - 1);       
        
        for (i = 0; i < n; ++i) {
            for (j = i; j < n; ++j) {
                res = Math.max(res, f[i][j]);
            }
        }
        
        return res;
    }
}

非递归方法

public class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        
        if (n == 1) {
            return 1;
        }
        
        int[][] f = new int[n][n];
        int i, j, len;
        for (i = 0; i < n; ++i) {
            f[i][i] = 1;
        }
        for (i = 0; i < n-1; ++i) {
            if (s.charAt(i) == s.charAt(i+1)) {
                f[i][i+1] = 2;
            }
            else {
                f[i][i+1] = 1;
            }
        }
        
        for (len = 3; len <= n; ++len) {
            for (i = 0; i <= n-len; ++i) {
                j = i + len - 1;
                f[i][j] = f[i][j-1];
                if (f[i+1][j] > f[i][j]) {
                    f[i][j] = f[i+1][j];
                }
                if (s.charAt(i) == s.charAt(j) && f[i+1][j-1] + 2 > f[i][j]) {
                    f[i][j] = f[i+1][j-1] + 2;
                }
            }
        }
        
        int res = 0;
        for (i = 0; i < n; ++i) {
            for (j = i; j < n; ++j) {
                if (f[i][j] > res) {
                    res = f[i][j];
                }
            }
        }
        
        return res;
    }
}

 

最长回文子串(Longest Palindrome Substring)

子串 (Substring):连续字符

数量级:O(n^2),一共有 1 + 2 +...+ n个非空子串,即 (n + 1) * n / 2

例:abcd

a b c d / ab bc cd / abc bcd / abcd

思路1 相向型双指针 O(n^3)

起点 O(n)  - - - - - - - - -(检测中间子串是否为回文串)O(n) - - - - - - - - - 终点 O(n)

a b c a           a b c a
^        ^   ==>    ^ ^    ==>  不相等结束
l         r              l  r

a b b a           a b b a         a b b a
^        ^   ==>    ^  ^    ==>     ^ ^     ==> 相遇结束
l         r              l   r                r l

public String longestPalindrome(String s) {
    if (s == null) {
        retrun null;
    }

    for (int length = s.length(); length >=1; length --) {
        for (int start = 0; start <= s.length() - length ; start++) {
            if (isPalindrome(s, start, start + length - 1)) {
                return s.substring(start, start + length);
            }
        }
    }

    return "";
}

public boolean isPalindrome(String s, int left, int right) {
    while (left < right && s.charAt(left) == s.charAt(right)) {
        left++:
        right--;
    }
    return left >= right;
}

思路2 枚举中心点 O(n^2)

t|a{bcb}a|c
避免重复检测bcb

tabcbac => t|a|b|b|a|c      t|a|b|b|a|c    t|a|b|b|a|--> L+1 ~ R-1
 <--|--> 长度为奇数,回文串中心点有 n 个
t|a|b|b|a|c => t|a|b|y|b|a|c     t|a|b|y|b|a|c      t|a|b|y|b|a|c    t|a|b|y|b|a|--> L+1 ~ R-1
  <--|--> 长度为偶数,回文串中心点有 n-1 个

public String longestPalindrome(String s) {
	if (s == null) {
		return null;
	}
	
	String longest = "";
	for (int i = 0; i < s.length(); i++) {
        // odd number
		String oddPalindrome = getPalindromeFrom(s, i, i);
		if (longest.length() < oddPalindrom.length()){
			longest = oddPalindrome;
		}
		
        //even number
		String evenPalindrome = getPalindromeFrom(s, i, i+1);
		if (longest.length() < evenPalindrome.length()){
			longest = evenPalindrome;
		}
	}
	
	return longest;
}

public String getPalindromeFrom(String s, int left, int right){
	while (left >=0 && right < s.length()) {
		if (s.charAt(left) != s.charAt(right)){
			break;
		}
		left--:
		right++;
	}
	
	return s.substring(left + 1, right);
}

思路3 动态规划 (Dynamic Programming)

动态规划:本阶段的状态是上一阶段状态和上一阶段决策的结果

状态转移方程:

已知 第K阶段的状态S_{k},第K阶段的决策u_{k}(S_{k})

如果 T_{k}(S_{k},u_{k}) 则 S_{k+1}= T_{k}(S_{k},u_{k}),即 S_{k+1}=u_{k}(S_{k})

设 [Row(r), Column(c)]  =  isPalindrome_{rc}

[0,0], [1,1], [2,2], [3,3], [4,4], [5,5], [6,6] => 单个字符一定是回文串                            [0,0], [1,1], [2,2], [3,3] => 单个字符一定是回文串 

[0,1], [1,2], [2,3], [3,4], [4,5], [5,6]          => 两个字符组合中没有回文串                     [0,1], [1,2], [2,3]          => 两个字符组合中有回文串

 倒序循环行,判断其余空单元格的布尔值,并且切割字符串起始位置指向True值区间较小值,回文串长度为True值区间值的个数(x_{b}-x_{a}+1

xabcbat
0123456
x Txa Fxab Fxabc Fxabcb Fxabcba Fxabcbat F0
nulla Tab Fabc Fabcb Fabcba Tabcbat F1
nullnullb Tbc Fbcb Tbcba Fbcbat F2
nullnullnullc Tcb Fcba Fcbat F3
nullnullnullnullb Tba Fbat F4
nullnullnullnullnulla Tat F5
nullnullnullnullnullnullt T6
abba
0123
a Tab Fabb Fabba T0
nullTbb Tbba F1
nullnullTba F2
nullnullnullT3
public String longestPalindrome(String s) {
    if (s == null || s.equals("")) {
        return "";
    }

    int n = s.length();
    boolean[][] isPalindrome = new boolean[n][n];
    
    int longest = 1, start = 0;
    //设置单个回文串状态
    for (int i = 0; i < n; i++) {
        isPalindrome[i][i] = true;
    }
    for (int i = 0; i< n - 1; i++) {
        isPalindrome[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        if (isPalindrome[i][i + 1]) {
            start = i;
            longest = 2;
        }
    }

    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 2; j < n; j++){
            isPalindrome[i][j] = isPalindrome[i + 1][j - 1] &&
                s.charAt(i) == s.charAt(j);

            if (isPalindrome[i][j] && j - i + 1 > longest) {
                start = i;
                longest = j - i + 1;
            }
        }
    }
    return s.substring(start, start + longest);
}

 

 

 

 

 

 

 

 

本文链接http://www.dzjqx.cn/news/show-617292.html