LeetCode-0407

115. 不同的子序列(困难)

思路

dp

当s[i] == t[j] 的时候，不难想到让dp[i][j] = dp[i-1][j-1]，这等于说，该位置字符compare成功了，就看之前的比较结果了，但是还要考虑，即使这一位可以比较成功，也要涵盖上之前匹配成功的结果，其他字串对于此位置可能也可以匹配成功，于是还要加上dp[i-1][j]，就是用t[0～j]去和s[0～i-1]比较的结果。

这题也保留了以往的预处理习惯，在前面加字符串进行处理。避免dp数组和字符串下标不一致的问题。这里可以加两个相同的字符串，因为dp[0][0] = 1;

要注意边界：预处理的时候，对于dp[i][0]和dp[0][j]的处理是不同的：因为长度为i的串可以包含空串，但是空串不能包含长度为j的串。所以dp[i][0] = 1；dp[0][j] = 0

并且还要注意，空集合是不包含空集合的，但是此处处理时dp[0][0]也要赋值为1。因为虽然空串之间不可以互相包含，但是空串之间是相等的，用以递推之后的串相等的匹配。此题两个串均非空，所以不用考虑空串包含问题。

/演草纸：bagbabgbagaij  1 1 1 1 1 1 1 10 1 1 2 2 3 3 30 0 1 1 1 1 4 4 0 0 0 0 1 1 1 5rabbbitb   1 1 1 1 1 1 10 2 2 2 2 2 20 0 3 3 3   */
class Solution {public int numDistinct(String s, String t) {s = "*"+s;t = "*"+t;int dp[][] = new int[s.length()][t.length()];for(int i=0;i<s.length();i++)dp[i][0] = 1;for(int j=1;j<t.length();j++){for(int i=1;i<s.length();i++){if(s.charAt(i) == t.charAt(j)){dp[i][j] = dp[i-1][j] + dp[i-1][j-1];}else {dp[i][j] = dp[i-1][j];}}}return dp[s.length()-1][t.length()-1];}//  不能用递归正向做，因为他找到一个就会停止
}

139. 单词拆分（中等）

思路：如果以word是以s[0~i]后缀，那么把s[i] = s[i - key.len]，问题转嫁成去判断之前的部分是否能够拼凑出来。

问题：一开始忘记将dp的赋值进行与运算了，可能会出现原本可以进行匹配的，被后来不能匹配的结果给覆盖掉了。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean dp[] = new boolean[s.length()+1];s = "*"+s;dp[0] = true;for(int i=1;i<s.length();i++){char st = s.charAt(i);for(String key:wordDict){if(i>=key.length()&&s.substring(i-key.length()+1,i+1).equals(key)){dp[i] = dp[i-key.length()]||dp[i];}}}return dp[s.length()-1];}
}

140. 单词拆分 II（困难）

思路：带一定存储功能的dp，和上一题相比，单一的dp数组不够了，需要创建一个节点类，记录可以的单词，之后还需要进行回溯。做的时候发现有些麻烦，或许直接进行正向的搜索更简单一些

问题：

• dp：定义类型的时候出了些问题，ArrayList声明二维数组也依然是new ArrayList<>()。然后回溯的时候特判一下开始，没有空格。
• 回溯：出了大问题，回溯的时候，一定不能改回溯需要的变量，一定不能出现在等号的左边进行赋值，例如sentence，如果赋值，又忘记删除掉（string也不好删除后缀，需要substr），之后会出现很多错，调了很久。

//	dp
//  直接深搜回溯可能更好一些
class Solution {class dpNode{boolean exist;String words;Integer last;public dpNode(boolean exist,String words,Integer last){this.exist = exist;this.words = words;this.last = last;}}public List<String> wordBreak(String s, List<String> wordDict) {s = "*"+s;List<List<dpNode>> dp = new ArrayList<>(s.length());dp.add(new ArrayList<>());dp.get(0).add(new dpNode(true,"",-1));for(int i=1;i<s.length();i++){dp.add(new ArrayList<>());for(String key:wordDict){if(i>=key.length()&&s.substring(i-key.length()+1,i+1).equals(key)){List<dpNode> temp = dp.get(i-key.length());if(temp.size()>0){dp.get(i).add(new dpNode(true,key,i-key.length()));}}}}List<String> res = new ArrayList<>();dfs(dp,s.length()-1,"",res);return res;}public void dfs(List<List<dpNode>>dp,int i,String sentence,List<String> res){if(i==0){res.add(sentence);return;}List<dpNode> tp = dp.get(i);for(dpNode key:tp){int len = key.words.length();if(sentence.length()==0){dfs(dp,i-len,key.words,res);   }else{dfs(dp,i-len,key.words+" "+sentence,res);   }}}
}

//	递归 回溯
class Solution {public List<String> wordBreak(String s, List<String> wordDict) {List<String> res = new ArrayList<>();dfs(s,wordDict,res,"");return res;}public void dfs(String s, List<String> wordDict,List<String> res,String sentence){if(s.length()==0) return;String blank = "";if(sentence!=""){blank = " ";}for(int i=0;i<wordDict.size();i++){String str = wordDict.get(i);if(str.length()>s.length())continue;if(s.substring(0,str.length()).equals(str)){if(s.equals(str)){res.add(sentence+blank+str);continue;}dfs(s.substring(str.length(),s.length()),wordDict,res,sentence+blank+str);}}}
}