判斷子序列
給定字符串 s 和 t ，判斷 s 是否為 t 的子序列钓株。
你可以認為 s 和 t 中僅包含英文小寫字母。字符串 t 可能會很長（長度 ~= 500,000）吊骤，而 s 是個短字符串（長度 <=100）捧存。
字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對位置形成的新字符串捷绒。（例如懦铺，"ace"是"abcde"的一個子序列捉貌，而"aec"不是）。
示例 1:
s =
"abc", t ="ahbgdc"
返回true.
示例 2:
s =
"axc", t ="ahbgdc"
返回false.
方法一：雙指針
i指向短串s，j指向長串t
- s[i]=t[j]趁窃，匹配i++,j++
- s[i]!=t[j] 牧挣，不匹配，用s[i]去匹配t[j]之后的元素,j++
如果i移動到了末尾醒陆，說明所有字符都匹配了
public boolean isSubsequence(String s, String t) {
int i=0;
int j=0;
while (i<s.length()&&j<t.length()){
if(s.charAt(i)==t.charAt(j)){
i++;
j++;
} else {
j++;
}
}
return i==s.length();
}
方法二：動態(tài)規(guī)劃
dp[i][j]表示s串到i位置與t串到j位置最長相同子序列的長度
- 當si =t j瀑构，dp[i][j]=dp[i-1][j-1]+1
- 當si !=t j,表示要刪除tj，則dp[i][j]=dp[i][j-1]
public boolean isSubsequence(String s, String t) {
int m = s.length(), n = t.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (s.charAt(i) == t.charAt(j)) {
dp[i + 1][j + 1] = dp[i][j] + 1;
} else {
dp[i + 1][j + 1] = dp[i + 1][j];
}
}
}
return dp[m][n] == m;
}
通過刪除字母匹配到字典里最長單詞
示例 1:
輸入:s = "abpcplea", d = ["ale","apple","monkey","plea"]
輸出: "apple"
示例 2:
輸入:s = "abpcplea", d = ["a","b","c"]
輸出: "a"
方法一：暴力回溯（超時）
public String findLongestWord(String s, List<String> d) {
StringBuilder sb=new StringBuilder();
findHelper(sb,s,d,0);
return ans;
}
private String ans="";
public void findHelper(StringBuilder sb,String s, List<String> d,int index){
if(index==s.length()){
String res=sb.toString();
if(d.contains(res)){
if (res.length() > ans.length() ||
(res.length() == ans.length() && res.compareTo(ans)<0)) {//注意字典序列
ans = res;
}
}
} else {
sb.append(s.charAt(index));//不刪
findHelper(sb,s,d,index+1);
sb.deleteCharAt(sb.length()-1);//刪
findHelper(sb,s,d,index+1);
}
}
方法二：轉換成判斷字典是否是串的子序列
因為要求返回最小的字典序列刨摩，所以需要先對字典排序
public String findLongestWord(String s, List<String> d) {
d.sort((o1, o2) -> o1.length() != o2.length() ? o2.length() - o1.length() : o1.compareTo(o2));
String ans = "";
for (String value : d) {
if (isSubsequence(value, s)) {
return value;
}
}
return ans;
}
public boolean isSubsequence(String s, String t) {
int i=0;
int j=0;
while (i<s.length()&&j<t.length()){
if(s.charAt(i)==t.charAt(j)){
i++;
j++;
} else {
j++;
}
}
return i==s.length();
}
時間復雜度：O(d×m×logd+d×(m+n))寺晌，其中 d 表示dictionary 的長度，m 表示 s 的長度澡刹，n 表示 dictionary 中字符串的平均長度
方法三：在是子序列的時候再排序
public String findLongestWord(String s, List<String> d) {
String ans="";
for (String word:d){
if(isSubsequence(word,s)){
if(word.length()>ans.length()||(word.length()==ans.length()&&word.compareTo(ans)<0)){
ans=word;
}
}
}
return ans;
}
時間復雜度：O(d×(m+n))折剃，其中 d 表示dictionary 的長度，m 表示 s 的長度像屋，n 表示 dictionary 中字符串的平均長度
