动态规划

  1. class Solution {
  2.     public boolean isSubsequence(String s, String t) {
  4.         boolean table[][] = new boolean[s.length() + 1][t.length() + 1];
  6.         for (int col=0; col<table[0].length; col++) {
  7.             table[0][col] = true;
  8.         }
  10.         for (int row=1; row<table.length; row++) {
  11.             char ch1 = s.charAt(row-1);
  12.             for (int col=1; col<table[row].length; col++) {
  13.                 char ch2 = t.charAt(col-1);
  14.                 if (ch1==ch2) {
  15.                     table[row][col] = table[row-1][col-1];
  16.                 } else {
  17.                     table[row][col] = table[row][col-1];
  18.                 }
  19.             }
  20.         }
  22.         boolean[] lastRow = table[table.length-1];
  23.         return lastRow[lastRow.length-1];
  24.     }
  25. }

参考链接： https://leetcode-cn.com/problems/is-subsequence/solution/shi-pin-jiang-jie-dong-tai-gui-hua-qiu-jie-is-subs/

双指针

  1. class Solution {
  2.     public boolean isSubsequence(String s, String t) {
  3.         int m = s.length();
  4.         int n = t.length();
  5.         int i = 0,j = 0;
  6.         while(i < m && j < n){
  7.             if(s.charAt(i) == t.charAt(j)){
  8.                 i++;
  9.             }
  10.             j++;
  11.         }
  12.         return i == m;
  13.     }
  14. }
  16. 作者：jovial-hugleufk
  17. 链接：https://leetcode-cn.com/problems/is-subsequence/solution/shuang-zhi-zhen-by-jovial-hugleufk-mogi/
  18. 来源：力扣（LeetCode）
  19. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。