思路：這題依舊比較容易揍拆，判斷s是否是t的子序列泞歉，我們依然可以用前幾天求共同子序列長(zhǎng)度的方法來解決雨女，只不過這題子序列固定為了s,最后求出來的長(zhǎng)度如果是s的長(zhǎng)度那么就可以匹配，如果不是那么就無法匹配曙痘，此外還需要在遞推公式中做出一點(diǎn)修改芳悲，我們之前在做最長(zhǎng)公共子序列的時(shí)候，當(dāng)遇到不匹配的情況需要考慮兩種情況 dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); 而本題中是用整個(gè)s去匹配t,那么當(dāng)不匹配時(shí)直接繼承t的前一位即可 dp[i][j] = dp[i][j-1];
class Solution {
public boolean isSubsequence(String s, String t) {
if(t.length() < s.length()) return false;
// dp[i][j]表示以i-1和j-1結(jié)尾的相同子序列長(zhǎng)度
int[][] dp = new int[s.length()+1][t.length()+1];
for (int i = 1; i < s.length()+1 ; i++) {
for (int j = 1;j < t.length() + 1;j++){
if (s.charAt(i - 1)== t.charAt(j-1)){
dp[i][j] = dp[i-1][j-1]+1;
}else {
// 不相等的時(shí)候直接繼承t的上一位的dp值 s的則不用動(dòng)
dp[i][j] = dp[i][j-1];
}
}
}
// 最后長(zhǎng)度相等 說明匹配
if (dp[s.length()][t.length()] == s.length()) return true;
return false;
}
}
