About Software: [LeetCode] 5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

<Solution>

這題有 DP 解法，也有專門算 palindromic substring 長度的演算法，叫 Manacher's Algorithm

DP 的想法是，用 dp[i][j] 表示從 s[i] 到 s[j] 是否是一個回文串

其公式如下：

當 s[i] = s[j] 的時候，如果是相鄰字元 (j - i < 2)，則 dp[i][j] = true

當 s[i] = s[j] 的時候，如果不是相鄰字元 (j - i >= 2)，則 dp[i][j] = dp[i+1][j-1]

當 s[i] != s[j] 的時候，則 dp[i][j] = false

code 如下

kotlin

	class Solution {
	fun longestPalindrome(s: String): String {
	val dp = Array(s.length) { BooleanArray(s.length) {false} }

	var ans = ""
	for(right in s.indices) {
	dp[right][right] = true
	for(left in 0..right) {
	if(s[left] == s[right] && (right-left < 2 \|\| dp[left+1][right-1])) {
	dp[left][right] = true
	}

	if(dp[left][right] && right - left + 1 > ans.length) {
	ans = s.substring(IntRange(left,right))
	}
	}
	}

	return ans
	}
	}

演算法說明 : ref1、ref2

使用 Manacher's Algorithm 來解這題，可以在 O(n) 裡面解完

C++

	class Solution {
	public:
	string longestPalindrome(string s) {
	//> use manacher's algorithm

	//> transform input
	string tranStr = "#";
	for(const auto &c : s) {
	tranStr += c;
	tranStr += '#';
	}

	int radis[tranStr.length()] = {0};
	int center = 0, maxRightIdx = 0;
	int maxIdx = 0, maxLen = 0;

	for(int i = 1; i < tranStr.length() - 1; i++) {
	radis[i] = (i < maxRightIdx) ? min(radis[2 * center - i], maxRightIdx - i) : 1;

	//> check palindrome substring
	while((i - radis[i]) >= 0 && (i + radis[i]) < tranStr.length()) {
	if(tranStr[i - radis[i]] == tranStr[i + radis[i]]) {
	radis[i]++;
	}
	else {
	break;
	}
	}

	//> update center and maxRightIdx
	if((i + radis[i] - 1) > maxRightIdx) {
	maxRightIdx = i + radis[i] - 1;
	center = i;
	}

	//> update maxIdx and maxLen
	if((radis[i] - 1) > maxLen) {
	maxLen = radis[i] - 1;
	maxIdx = i;
	}
	}

	int originalIdx = (maxIdx - maxLen) / 2;
	return s.substr(originalIdx, maxLen);
	}
	};

Java

	public class Solution {
	public String longestPalindrome(String s) {
	//>> use manacher's algorithm

	//>> transform string
	String tranStr = "#";
	for(int i = 0; i < s.length(); i++) {
	tranStr = new StringBuilder(tranStr).append(s.charAt(i)).append('#').toString();
	}

	int[] radis = new int[tranStr.length()];
	int center = 0, maxRightIdx = 0;
	int maxIdx = 0, maxLen = 0;
	final int len = tranStr.length();

	for(int i = 1; i < len-1; i++) {
	radis[i] = (i < maxRightIdx) ? Math.min(radis[2*center-i], maxRightIdx-i) : 1;

	//> check palindrome substring
	while((i-radis[i]) >= 0 && (i+radis[i]) < len) {
	if(tranStr.charAt(i-radis[i]) == tranStr.charAt(i+radis[i])) {
	radis[i]++;
	}
	else {
	break;
	}
	}

	//> update center and maxRightIdx
	if((i+radis[i]-1) > maxRightIdx) {
	maxRightIdx = i + radis[i] - 1;
	center = i;
	}

	//> update maxIdx and maxLen
	if((radis[i]-1) > maxLen) {
	maxLen = radis[i] - 1;
	maxIdx = i;
	}
	}

	int originalIdx = (maxIdx - maxLen) / 2;
	return s.substring(originalIdx, originalIdx+maxLen);
	}
	}

About Software