392. 判断子序列

【题目】判断s字符串是不是t字符串的子序列
【分析】遍历t字符串的同时，增加一个游标来标记s字符串的位置，若遇到相等的则二者都向前索引，同时判断s是不是到头。
【拓展】该题目是可以利用最长公共子序列来求解的，判断最长公共子序列和s字符串是不是相等就行了。

  1. class Solution {
  2.     public boolean isSubsequence(String s, String t) {
  3.         if (s.length() == 0) return true;
  4.         if (s.length() > t.length()) return false;
  6.         int sIndex = 0;
  7.         for (int i=0; i<t.length(); i++) {
  8.             if (s.charAt(sIndex) == t.charAt(i)) {
  9.                 sIndex++;
  10.                 if (sIndex == s.length()) return true;
  11.             }
  12.         }
  13.         return false;
  14.     }
  15. }
  1. //拓展
  2. class Solution {
  3.     public boolean isSubsequence(String s, String t) {
  4.         if (s.length() == 0) return true;
  5.         if (s.length() > t.length()) return false;
  6.         return longestCommonSubsequence(s, t) == s.length();
  7.     }
  8.     public int longestCommonSubsequence(String text1, String text2) {
  9.         int m = text1.length();
  10.         int n = text2.length();
  11.         int[][] dp = new int[m+1][n+1]; //text1[0:i)和text2[0:j)的最长公共子序列长度
  12.         for (int i=1; i<=m; i++) {
  13.             for (int j=1; j<=n; j++) {
  14.                 if (text1.charAt(i-1) == text2.charAt(j-1)) {
  15.                     dp[i][j] = dp[i-1][j-1] + 1;
  16.                 } else {
  17.                     dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
  18.                 }
  19.             }
  20.         }
  21.         return dp[m][n];
  22.     }
  23. }

491. 递增子序列

【题目】给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是 2 。
【分析】使用递归+回溯的思路找到子序列的所有递增子序列，因为是子序列问题，所以，当前元素是可加可不加的，所以就出现了下面的两种递归。

  1. class Solution {
  2.     List<List<Integer> > res = new LinkedList<>();
  3.     public List<List<Integer>> findSubsequences(int[] nums) {
  4.         LinkedList<Integer> temp = new LinkedList<>();
  5.         dfs(nums, temp, 0, -101);
  6.         return res;
  7.     }
  8.     public void dfs(int[] nums, LinkedList<Integer> temp, int cur, int preNum) {
  9.         //递归+回溯
  10.         if (cur == nums.length) {
  11.             if (temp.size() >= 2) {
  12.                 res.add(new LinkedList<>(temp));
  13.             }
  14.             return;
  15.         }
  16.         //以下两种情况都要执行到
  17.         //1. 选择该元素
  18.         if (nums[cur] >= preNum) {
  19.              temp.add(nums[cur]);
  20.             dfs(nums, temp, cur+1, nums[cur]);
  21.             temp.removeLast();
  22.         }
  23.         //2. 不选择该元素，加入判等是为了避免出现重复
  24.         if (nums[cur] != preNum) {
  25.             dfs(nums, temp, cur+1, preNum);
  26.         }    
  27.     }
  28. }