LeetCode Problem Link

https://leetcode.com/problems/is-subsequence

Intuition

  • looks similar to the Leetcode 383 Ransom Note but it is different because it also care about the order of subsequence => s=”abc”, t=”axcba”: false! 
          std::array<int, 26> freq = {0};
      for (auto c : t) {
          freq[c-'a']++;
      }
      for (auto c : s) {
          if (--freq[c-'a']<0) {
              return false;
          }
      }
      return true;
  • so is it a two-pointer? no, it has no symmetrical features at all. (and actually it requires four pointers) 
          int head = 0;
      int tail = t.length()-1;
      int hd = 0;
      int tl = s.length()-1;
      while(hd<=tl && head<tail) {
          if (t[head] != s[hd]) {
              ++head;
              continue;
          }
          else if (t[tail] != s[tl]) {
              --tail;
              continue;
          }
          ++hd;
          --tl;
          ++head;
          --tail;
      }
      if (hd<tl) return false;
      if (hd==tl && s[hd]!=t[head]) return false;
      return true;

Approach

  • normal iteration is sufficient and much simpler! 
          int s_i = 0;
      for (int i=0;s_i<s.length() && i<t.length();++i) {
          if (s[s_i] != t[i]) {
              continue;
          }
          ++s_i;
      }
      if (s_i != s.length()) return false;
      return true;
  • if the number of s strings is huge, then store the indices of the same letter and use them to move the pointer to the next position

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code

#if 0
    bool isSubsequence(string s, string t) {
        std::vector<int> pos[26];
        for (int i=0;i<t.length();++i) {
            pos[t[i]-'a'].push_back(i);
        }
        int s_i = -1;
        for (auto c : s) {
            const auto& indices = pos[c-'a'];   // {0, 3, ...}
            auto it = std::upper_bound(begin(indices), end(indices), s_i);
            if (it == end(indices)) {
                return false;
            }
            s_i = *it;
        }
        return true;
    }
#endif
#if 1
    bool isSubsequence(string s, string t) {
        int s_i = 0;
        for (int i=0;s_i<s.length() && i<t.length();++i) {
            if (s[s_i] != t[i]) {
                continue;
            }
            ++s_i;
        }
        if (s_i != s.length()) return false;
        return true;
    }
#endif

GitHub

is-subsequence