Related:

Subsequence Definition

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. 

s(source) is a subsequence of t(target) :

  • s.length() <= t.length()
  • t要包含s里面的所有的chars
  • s为t删掉一些char产生的
  • 目的是: 确保s中的所有的char都按顺序出现在t中 -> 按s的顺序遍历, 对于每一个s[i]都要在t中找到match

392. Is Subsequence

Greedy - recursion

  • 当s.charAt(i) != t.charAt(j)时 -> 当前的s[i]没有被t[j]match上, 跳过t[j], 看t[j+1]是否能够match上s[i] => 对s[i, slen) 和 t[j + 1, tlen)继续进行判断
  • 当s.charAt(i) == t.charAt(j)时 -> 当前的s[i]已经被t[i]match上了 => 同时跳过s[i]和t[j], 对s[i + 1, slen) 和 t[j + 1, tlen)继续进行判断
    • 这样match的其实是一个maximum window subsequence, e.g.
      • "abc" / "xaaxbxc" -> match的subsequence是"aaxbxc" (min window subsequence是"axbxc"
    • 所以不需要对s[i + 1, slen) / t[j + 1, tlen) 和 s[i, slen)/t[j + 1, tlen) (可以找到min windwo subsequence) 同时判断, 都判断的话会TLE
  • 总结: 无论s[i]是否等于t[j], j指针永远都往右走; 只有当s[i] == t[j]时, 才移动i指针 -> 只有当match了, 才移动s的指针
  • 最终判断
    • 当i到达s末尾时 -> s match完毕, s中所有的chars均已经按顺序出现在了t中 -> s为t的subsequence
    • 当j到达t末尾 && i未达到s末尾 -> s中仍有chars不存在t中 -> s不是t的subsequence
  • Time: O(T) -> S和T中较长的string length 而因为S <= T 所以是T / Space: O(T) stack depth
 public boolean isSubsequence(String s, String t) {     return helper(s, 0, t, 0); } private boolean helper(String s, int i1, String t, int i2) {     if (i1 == s.length()) return true;     if (i2 == t.length()) return false;     if (s.charAt(i1) == t.charAt(i2)) i1 ++;     i2 ++;     return helper(s, i1, t, i2); }

Two pointers - Iterative

用同向双指针来实现Greedy的recursion的方法

  • 2个指针同时从s和t的头部开始往尾部扫 : i = 0 / j = 0
    • s[i] == t[j] -> i ++/ j ++ => t[j] match s[i], 跳过s[i]/t[j]继续寻找s[i + 1]的match
    • s[i] != t[j] -> j ++ => 当前t[j]不match s[i], 跳过t[j]继续寻找s[i]的match
  • 对最终的i和j停留的位置进行判断s是否是t的subsequence
  • Time: O(T) / Space: O(1) -> 比greedy 优化了space
 public boolean isSubsequence(String s, String t) {     int i1 = 0, i2 = 0;     while(i1 < s.length() && i2 < t.length()) {         if (s.charAt(i1) == t.charAt(i2)) i1 ++;         i2 ++;     }     return i1 == s.length(); }

Dynamic Programming - 1

我觉得dp的思维和greedy的思维似乎有点不一样

  • greedy: 从当前s[i]/t[j]是否相等的情况往后推
  • dp: 从当前s[i]/t[j]是否相等 和 s[0, i - 1]/t[0, j - 1]的情况 来推导之后的情况
  • 在source中, 从0到slen看是否为t的subsequence的过程
  • dp[i][j]表示s[0, ith] char是否为t[0, jth] char的subsequence ->
    • if s[i] == t[j] => dp[i][j] = dp[i - 1][j - 1]
      • 若s[i]和t[j]相等 -> 则s[0, i]/t[0, j]的匹配状况和s[0, i - 1]/t[0, j - 1]相同
    • if s[i] != t[j] => dp[i][j] = dp[i][j - 1]
      • 这个我不太会想, 这么想跟dp[i][j]有关系的前面的值就这么3个: dp[i-1][j-1]/dp[i-1][j]/dp[i][j - 1]
        • dp[i][j]和dp[i - 1][j]和dp[i - 1][j - 1]dp[i][j]都没什么关系
        • dp[i][j - 1]: s[0, i]/t[0, j]的match情况就和s[0, i]/t[0, j - 1]的match情况一样 -> 因为t[j]没match上s[i]所以t[j]这个char就变成了可有可无可被删除的那个char
  • source为row / target为col -> 从source开始loop 起 => 从s[0, i]在整个t中找subsequence匹配的过程
  • dp[][] = boolean[slen + 1][tlen + 1];
  • NOTE:这里要把dp[0][j]均初始化为True. 因为"" 可以匹配所有的string
  • res = dp[slen][tlen]
  • Time: O(S * T) / Space: O(S * T)
 public boolean isSubsequence(String s, String t) {     int slen = s.length();     int tlen = t.length();     boolean[][] dp = new boolean[slen + 1][tlen + 1];     for(int j = 0; j <= tlen; j ++) {         dp[0][j] = true;     }     for(int i = 0; i < slen; i ++) {         for(int j = 0; j < tlen; j ++) {             if (s.charAt(i) == t.charAt(j)) {                 dp[i + 1][j + 1] = dp[i][j];             } else {                 dp[i + 1][j + 1] = dp[i + 1][j];             }         }     }     return dp[slen][tlen]; }

char indices(HashMap) + binary search

以上的解法在当存在很多s要判断是否si是t的subsequence的时候时间复杂度均比较高, 无论si的长短或者是否出现过, 一直都要扫描整个t, 引入一个Map<Character, List<Integer>> 来存每一个char在t里面的index, 之后呢?

  • 一个index代表当前在t的位置
  • loop through s string, 对于s中每一个c, 找到第一个> index的值 i', update index = i' => 这里可以引入binary search
  • 直到s都loop 完毕 => return true/ 否则false

具体应用在下面的题目里

792. Number of Matching Subsequences

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

  • For example, "ace" is a subsequence of "abcde".

利用char indices(HashMap) + binary search

Time: O(S + N * logS) N为words中所有word的总长度 / Space: O(S) 

 public int numMatchingSubseq(String s, String[] words) {     Map<Character, List<Integer>> map = new HashMap<>();     int slen = s.length();     for(int i = 0; i < slen; i ++) {         char c = s.charAt(i);         map.putIfAbsent(c, new ArrayList<Integer>());         map.get(c).add(i);     }     int res = 0;     for(String w : words) {         if (isSubsequence(w, map, s);)             res ++;     }     return res; } private boolean isSubsequence(String w, Map<Character, List<Integer>> map, String s) {     int index = -1;     int i = 0;     int len = w.length();     while(i < len) {         char c = w.charAt(i);         if (!map.containsKey(c)) return false;         int nextIndex = findNextIndex(index, map.get(c));         if (nextIndex == -1) return false;         index = nextIndex;         i ++;     }     return true; } private int findNextIndex(int cur, List<Integer> list) {     int start = 0;     int end = list.size() - 1;     while(start + 1 < end) {         int mid = start + (end - start) / 2;         if (list.get(mid) > cur) {             end = mid;         } else {             start = mid;         }     }     if (list.get(start) > cur) return list.get(start);     if (list.get(end) > cur) return list.get(end);     return -1; }

char 剥除法?

loop through s -> 对于每一个c, 把words中以c开头的word删除掉c (表明word中的第一个char已经在s中被match了) 直到一个word被删完, 说明它的所有的chars都在s中出现过了. 实现

  • 一个Map key为Character, value 为?
    • value 为一个queue, 因为需要从里面poll和加入新的刚被处理过的w
  • 首先把所有words放到map里面
  • loop through s, 对于每一个c
    • 从map里面取出word queue -> 所有的以c开头的word
    • 把这些word的第一个c都删掉, 根据删掉剩下的word的第一个char放到相应的map里
      • NOTE: !!!注意这里不能一直不停的取queue里面的元素, 只能取出当前的words, 后来加入的不能再取. 所以要用queue.size()作为约束而不能用!queue.isEmtpy()
    • 如果当前的word只剩一个char, 则已经match完毕, 找到一个subsequence, count ++
  • 这里也可以自己建一个class来存一些东西
  • Time: O(S + N) N为words里面所有word的char的总数
  • Space: O(words.length) 当优化掉substring而使用一个pointer来表示当前的word match到了哪的时候
    • HashMap是constant space 26 -> O(1)
    • 之后的space就是对于每个c从map里面出来的queue的长度, 这个queue的最大长度即为words.length
    • 当使用substring时: Space: O(N) N为words 里面所有word 的char的总数
 public int numMatchingSubseq(String s, String[] words) {     Map<Character, Queue<String>> map = new HashMap<>();     for(int i = 0; i < 26; i ++) {         map.put((char)(i + 'a'), new LinkedList<String>());     }     for(String w : words) {         map.get(w.charAt(0)).offer(w);     }     int res = 0;     for(char c : s.toCharArray()) {         Queue<String> queue = map.get(c);         int size = queue.size();         for(int i = 0; i < size; i ++){             String cur = queue.poll();             if (cur.length() == 1) {                 res ++;             } else {                 map.get(cur.charAt(1)).offer(cur.substring(1, cur.length()));             }         }     }     return res; }
This free site is ad-supported. Learn more
​