10. Regular Expression Matching
这道题的难点在于各种情况的讨论 dp[i][j]表示s的前i个字符能不能和p的前j个字符match上
如何运用之前的结果比如dp[i][j-1] dp[i-1][j]推得当前dp[i][j]结果
（1）如果当前的字符一样 则完全取决于(i-1,j-1)
（2）如果当前的P是“*” 如果P的前面一个字符等于S当前字符 可以是直接等于也可以是间接的“.”分为三种情况讨论
public class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
//dp(i,j) whether the first # of i element match with the first # of j element
boolean[][] dp = new boolean[m + 1][n + 1];
//empty match
dp[0][0] = true;
//base case
for(int i = 2;i <= n;i++){
//the dp[i][j-2]only requires when curP == '*'
if(p.charAt(i-1) == '*'){
dp[0][i] = dp[0][i-2];
}
}
//Iteration
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
char curS = s.charAt(i-1);
char curP = p.charAt(j-1);
if(curP == curS || curP == '.'){
dp[i][j] = dp[i-1][j-1];
}
else if(curP == '*'){
char prevP = p.charAt(j-2);
if(prevP == '.'||prevP == curS){
//'.'等价于preP == CurS
//取1一个,取0个,无限match
dp[i][j] = dp[i][j-1]||dp[i][j-2]||dp[i-1][j];
}
else{
dp[i][j] = dp[i][j-2];
}
}
}
}
return dp[m][n];
}
}
44. Wildcard Matching
p[i] == "*" 两种情况 取任意多个 看dp(i-1,j) 还有就是什么都不取 看dp(i,j) 同样的base case结合递推式里面的判断
条件写！可以说是LC10的简化版本
public class Solution {
public boolean isMatch(String s, String p) {
if (p == null || p.length() == 0) {
return s == null || s.length() == 0;
}
int rows = s.length();
int cols = p.length();
boolean[][] dp = new boolean[rows + 1][cols + 1];
dp[0][0] = true;
for (int j = 1; j <= cols; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 1];
}
}
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
if (p.charAt(j - 1) != '*') {
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1];
}
} else {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}
}
}
return dp[s.length()][p.length()];
}
}
161. One Edit Distance
One edit 所以长度差最多为 1.然后分情况讨论 如果有一个字符mismatch 当两个string长度相等的时候 直接判断两个string 剩下的是否一致。 当两个string长度相差1的时候 只能有一个操作 而这个操作不能用在直接exchange element上面 所以只能是
删除字符操作这样 就需要保持 s.substr(i+1)和t(i)相等 比如ABCD 和 ACD. 如果没有mismatch 则判断是不是长度相差 1 这样
就是直接删除
/** One edit distance means that the strings have one different index
* Edit the first version by deleting the duplicated code */
public class Solution {
public boolean isOneEditDistance(String s, String t) {
int len1 = s.length();
int len2 = t.length();
if(Math.abs(len1 - len2) > 1)return false;
//check for mismatch
for(int i = 0;i < Math.min(len1,len2);i++){
if(s.charAt(i) != t.charAt(i)){
if(len1 == len2){
return s.substring(i + 1).equals(t.substring(i + 1));
}
if(len1 > len2){
return s.substring(i + 1).equals(t.substring(i));
}
else{
return s.substring(i).equals(t.substring(i + 1));
}
}
}
//if there are no mismatch then the two strings have 1 edit distance only
//if the length difference is 1
return Math.abs(len1 - len2) == 1;
}
}
72. Edit Distance
follow up问题可以看 http://blog.csdn.net/linhuanmars/article/details/24213795
注意到这类问题在定义DP(i,j)的时候都是前i个和前j个匹配 是元素的个数 然后这里还是借鉴了前面的结果 加1或者替换 加和
删除是镜像的 所以只考虑加就行了
public class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int[][] dis = new int[len1+1][len2+1];
//base case
dis[0][0] = 0;
for(int i = 1;i <= len2;i++){
dis[0][i] = i;
}
for(int i =1 ;i <= len1;i++){
dis[i][0] = i;
}
//Iteration
for(int i = 1;i < len1+1;i++){
for(int j = 1;j < len2+1;j++){
if(word1.charAt(i-1) == word2.charAt(j-1)){dis[i][j] = dis[i-1][j-1];}
else{
dis[i][j] = Math.min(Math.min(dis[i][j-1] + 1,dis[i-1][j] + 1),dis[i-1][j-1]+1);
}
}
}
return dis[len1][len2];
}
}
139. Word Break
We were given an dictionary contains words and find whether a string could be break into words constructed by
the given dictionary words only? We could also use the history result. Such as whether the first m element of
the string is breakable and how we extend the result to larger index m(m > n) We can check whether any words right
indexed with n exist in the dictionary and if there are DP[i] = D[j].
We can calculate the maximum length of the given strings to reduce some unnecessary search. Be patient with the index
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
//P[i] defines whether the first # i element is breakable
if(s == null || s.length() == 0) return false;
int len = s.length();
//Build a HashSet from the ArrayList and calculate the maximum Length among the strings of
HashSet<String> set = new HashSet();
int maxLen = 0;
for(String str : wordDict){
set.add(str);
maxLen = Math.max(maxLen,str.length());
}
boolean[] P = new boolean[len + 1];
//Base case
P[0] = true;
//Iteration
for(int i = 1;i <= len;i++){
for(int j = Math.max(0,i - maxLen);j < i;j++){
if(P[j] == false)continue;
String sub = s.substring(j,i);
if(set.contains(sub))P[i] = true;
}
}
return P[len];
}
}
97. Interleaving String
同样的是字符串组合能否成为第三个字符串问题 这里的DP不用是三维的 因为两个维度就可以确认匹配S3的前K个字符 利用当前S3的字符
是否和S1或者S2的字符匹配 然后借用前面的结果 (i-1,j)是否能match到相应的s3
时间复杂度是O(len1)*O(len2)
这道题也可以用一维的去做 http://blog.csdn.net/linhuanmars/article/details/24683159 只不过对我来说不太懂
/** memo(i,j) describe whether the first i element in s1 and the first s2 element in s2
* could form the first (i + j) th element in s3. We do not need another array to state the
* relationship **/
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int l1 = s1.length();
int l2 = s2.length();
int l3 = s3.length();
if((l1 + l2) != l3)return false;
boolean[][] memo = new boolean[l1 + 1][l2 + 1];
//base case
memo[0][0] = true;
for (int i = 1; i <= s1.length(); i++) {
if(s3.charAt(i - 1) == s1.charAt(i - 1) && memo[i-1][0])
memo[i][0] = true;
}
for (int j = 1; j <= s2.length(); j++) {
if(s3.charAt(j - 1) == s2.charAt(j - 1) && memo[0][j - 1])
memo[0][j] = true;
}
//Iteration
for(int i = 1;i <= l1;i++){
for(int j = 1;j <= l2;j++){
int k = i + j;
if((s3.charAt(k - 1) == s1.charAt(i - 1) && memo[i - 1][j] || s3.charAt(k - 1) == s2.charAt(j - 1)&& memo[i][j - 1])){
memo[i][j] = true;
}
}
}
return memo[l1][l2];
}
}