Interleaving String
Total Accepted: 7740
Total Submissions: 41615 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
状态定义:
dp[i][j]:= s1的前i和字串和s2和前j个字串是否构成交替字符串
状态转移：
dp_state[i][j] = (dp_state[i-1][j] && (s1[i-1] == s3[i+j-1])) || (dp_state[i][j-1] && (s2[j-1] == s3[i+j-1]));
说明：分两种情况，对于当前第i+j个字符来说，若选择s[i]，则必须满足 s3[i+j-1] == s1[i-1] && dp[i-1][j] == true，另一种情况同理。
状态初始化：
dp[0][0] = true;
dp_state[i][0] = dp_state[i-1][0] && (s3[i-1] == s1[i-1]);
(i = 1;
i <= len1;
)
dp_state[0][i] = dp_state[0][i-1] && (s3[i-1] == s2[i-1]);
(i = 1;
i <= len2;
)
代码：
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size(), len2 = s2.size(), len3 = s3.size();
if ((len1 + len2) != len3)
{
return false;
}
bool** dp_state = new bool*[len1 + 1];
for (int i = 0;
i <= len1;
i++)
{
dp_state[i] = new bool[len2+1];
}dp_state[0][0] = true;
for (int i = 1;
i <= len1;
i++)
{
dp_state[i][0] = dp_state[i-1][0] && (s3[i-1] == s1[i-1]);
}
for (int i = 1;
i <= len2;
i++)
{
dp_state[0][i] = dp_state[0][i-1] && (s3[i-1] == s2[i-1]);
}
for (int i = 1;
i <= len1;
i++)
{
for (int j = 1;
j <= len2;
j++)
{dp_state[i][j] = (dp_state[i-1][j] && (s1[i-1] == s3[i+j-1])) || (dp_state[i][j-1] && (s2[j-1] == s3[i+j-1]));
}
}
bool ret = dp_state[len1][len2];
for (int i = 0;
i <= len1;
i++)
{
delete[] dp_state[i];
}
delete []dp_state;
return ret;
}
};
Longest Palindromic Substring
Total Accepted: 10323 Total Submissions: 50456 Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
这题的思路来自： X Wang dp[i][j] 定义为字串s[i, j]是否为回文.
dp[i][j] = 1 当且仅当 dp[i+1][j-1] == 1 && s[i] == s[j]
【Algorithm-动态规划|【字符串动态规划】最长回文字串+交替字符串】代码如下：c++的代码超时，java的 AC
class Solution {
public:
string longestPalindrome(string s)
{
if (s == "" || s == " ")
{
return s;
}
int maxLen = 0;
string ret;
int size = s.size();
bool** dp = new bool*[size];
for (int i = 0;
i < size;
i++)
{
dp[i] = new bool[size];
}
for (int i = 0;
i < size;
i++)
{
dp[i][i] = true;
}
for (int i = 0;
i < size-1;
i++)
{
if (s[i] == s[i+1])
{
dp[i][i+1] = 1;
ret = s.substr(i, 2);
maxLen = 2;
}
}
for (int L = 3;
L <= size;
L++)
{
for (int i = 0;
i <= size - L;
i++)
{
int j = i+L-1;
if (s[i] == s[j])
{
dp[i][j] = dp[i+1][j-1];
if (dp[i][j] == 1 && L > maxLen)
{
maxLen = L;
ret = s.substr(i, L);
}
}
else dp[i][j] = 0;
}
}
for (int i = 0;
i < size;
i++)
{
delete[] dp[i];
}
delete[]dp;
return ret;
}};
java:
public class Solution {
public String longestPalindrome(String s) {
if (s == null)
return null;
if(s.length() <=1)
return s;
int maxLen = 0;
String longestStr = null;
int length = s.length();
boolean[][] table = new boolean[length][length];
for (int i = 0;
i < length;
i++) {
table[i][i] = true;
}
for (int i = 0;
i <= length - 2;
i++) {
if (s.charAt(i) == s.charAt(i + 1)){
table[i][i + 1] = true;
longestStr = s.substring(i, i + 2);
maxLen = 2;
}
}
for (int l = 3;
l <= length;
l++) {
for (int i = 0;
i <= length-l;
i++) {
int j = i + l - 1;
if (s.charAt(i) == s.charAt(j)) {
table[i][j] = table[i + 1][j - 1];
if (table[i][j] == true && l > maxLen)
{
longestStr = s.substring(i, j + 1);
maxLen = l;
}
} else {
table[i][j] = false;
}
}
}
return longestStr;
}
}
