LeetCode:392.判断子序列
1.思路
暴力解法，循环遍历，当s和t字符串中字符相同时，对其当前位置与s的长度判断是否相同，如果相同返回true，否则更新遍历s字符串的位置，继续遍历。如果遍历结束没有返回true，则返回false。
2.代码实现
class Solution { public boolean isSubsequence(String s, String t) { if (s.length() > t.length()) { return false; } if (s.length() == 0 || s == null) { return true; } int location = 0; for (int i = 0; i < t.length(); i++) { if ((t.charAt(i) - '0') == (s.charAt(location) - '0')) { if (location == s.length() - 1) { return true; } location++; } } return false; } } // 动规 class Solution { public boolean isSubsequence(String s, String t) { int lens = s.length(); int lent = t.length(); int[][] dp = new int[lens + 1][lent + 1]; // 遍历初始化 // dp[][0] = 0; // dp[0][] = 0; // 错误例子 for (int i = 1; i <= lens; i++) { for (int j = 1; j <= lent; j++) { if (s.charAt(i - 1) == t.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = dp[i][j - 1]; } } } if (dp[lens][lent] == lens) { return true; } return false; } }
3.复杂度分析
时间复杂度：O(n).
空间复杂度：O(1).
LeetCode:115.不同的子序列
1.思路
dp[i][j]表示i-1,j-1下s中拥有子串t的个数，便于初始化，当s不为null且t为null时，应该将dp[i][0]=1,其他部分默认为0.
递推公式：当前遍历元素相同时，dp[i][j]=dp[i-1][j-1] + dp[i-1][j];
不相同时dp[i][j]=dp[i-1][j];
2.代码实现
class Solution { public int numDistinct(String s, String t) { int[][] dp = new int[s.length() + 1][t.length() + 1]; // 其他部分全部默认为0 for (int i = 0; i < s.length(); i++) { dp[i][0] = 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] + dp[i - 1] [j]; } else { dp[i][j] = dp[i - 1][j]; } } } return dp[s.length()][t.length()]; } }
3.复杂度分析
时间复杂度：O(m*n).
空间复杂度：O(n).
