Question

792. Number of Matching Subsequences

中文文档

Description

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".

 

Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

 

Constraints:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.

Solutions

Solution 1

class Solution:
  def numMatchingSubseq(self, s: str, words: List[str]) -> int:
    d = defaultdict(deque)
    for w in words:
      d[w[0]].append(w)
    ans = 0
    for c in s:
      for _ in range(len(d[c])):
        t = d[c].popleft()
        if len(t) == 1:
          ans += 1
        else:
          d[t[1]].append(t[1:])
    return ans

class Solution {
  public int numMatchingSubseq(String s, String[] words) {
    Deque<String>[] d = new Deque[26];
    Arrays.setAll(d, k -> new ArrayDeque<>());
    for (String w : words) {
      d[w.charAt(0) - 'a'].add(w);
    }
    int ans = 0;
    for (char c : s.toCharArray()) {
      var q = d[c - 'a'];
      for (int k = q.size(); k > 0; --k) {
        String t = q.pollFirst();
        if (t.length() == 1) {
          ++ans;
        } else {
          d[t.charAt(1) - 'a'].offer(t.substring(1));
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int numMatchingSubseq(string s, vector<string>& words) {
    vector<queue<string>> d(26);
    for (auto& w : words) d[w[0] - 'a'].emplace(w);
    int ans = 0;
    for (char& c : s) {
      auto& q = d[c - 'a'];
      for (int k = q.size(); k; --k) {
        auto t = q.front();
        q.pop();
        if (t.size() == 1)
          ++ans;
        else
          d[t[1] - 'a'].emplace(t.substr(1));
      }
    }
    return ans;
  }
};

func numMatchingSubseq(s string, words []string) (ans int) {
  d := [26][]string{}
  for _, w := range words {
    d[w[0]-'a'] = append(d[w[0]-'a'], w)
  }
  for _, c := range s {
    q := d[c-'a']
    d[c-'a'] = nil
    for _, t := range q {
      if len(t) == 1 {
        ans++
      } else {
        d[t[1]-'a'] = append(d[t[1]-'a'], t[1:])
      }
    }
  }
  return
}

Solution 2

class Solution:
  def numMatchingSubseq(self, s: str, words: List[str]) -> int:
    d = defaultdict(deque)
    for i, w in enumerate(words):
      d[w[0]].append((i, 0))
    ans = 0
    for c in s:
      for _ in range(len(d[c])):
        i, j = d[c].popleft()
        j += 1
        if j == len(words[i]):
          ans += 1
        else:
          d[words[i][j]].append((i, j))
    return ans

class Solution {
  public int numMatchingSubseq(String s, String[] words) {
    Deque<int[]>[] d = new Deque[26];
    Arrays.setAll(d, k -> new ArrayDeque<>());
    for (int i = 0; i < words.length; ++i) {
      d[words[i].charAt(0) - 'a'].offer(new int[] {i, 0});
    }
    int ans = 0;
    for (char c : s.toCharArray()) {
      var q = d[c - 'a'];
      for (int t = q.size(); t > 0; --t) {
        var p = q.pollFirst();
        int i = p[0], j = p[1] + 1;
        if (j == words[i].length()) {
          ++ans;
        } else {
          d[words[i].charAt(j) - 'a'].offer(new int[] {i, j});
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int numMatchingSubseq(string s, vector<string>& words) {
    vector<queue<pair<int, int>>> d(26);
    for (int i = 0; i < words.size(); ++i) d[words[i][0] - 'a'].emplace(i, 0);
    int ans = 0;
    for (char& c : s) {
      auto& q = d[c - 'a'];
      for (int t = q.size(); t; --t) {
        auto [i, j] = q.front();
        q.pop();
        if (++j == words[i].size())
          ++ans;
        else
          d[words[i][j] - 'a'].emplace(i, j);
      }
    }
    return ans;
  }
};

func numMatchingSubseq(s string, words []string) (ans int) {
  type pair struct{ i, j int }
  d := [26][]pair{}
  for i, w := range words {
    d[w[0]-'a'] = append(d[w[0]-'a'], pair{i, 0})
  }
  for _, c := range s {
    q := d[c-'a']
    d[c-'a'] = nil
    for _, p := range q {
      i, j := p.i, p.j+1
      if j == len(words[i]) {
        ans++
      } else {
        d[words[i][j]-'a'] = append(d[words[i][j]-'a'], pair{i, j})
      }
    }
  }
  return
}

Solution 3

class Solution:
  def numMatchingSubseq(self, s: str, words: List[str]) -> int:
    def check(w):
      i = -1
      for c in w:
        j = bisect_right(d[c], i)
        if j == len(d[c]):
          return False
        i = d[c][j]
      return True

    d = defaultdict(list)
    for i, c in enumerate(s):
      d[c].append(i)
    return sum(check(w) for w in words)

class Solution {
  private List<Integer>[] d = new List[26];

  public int numMatchingSubseq(String s, String[] words) {
    Arrays.setAll(d, k -> new ArrayList<>());
    for (int i = 0; i < s.length(); ++i) {
      d[s.charAt(i) - 'a'].add(i);
    }
    int ans = 0;
    for (String w : words) {
      if (check(w)) {
        ++ans;
      }
    }
    return ans;
  }

  private boolean check(String w) {
    int i = -1;
    for (int k = 0; k < w.length(); ++k) {
      int c = w.charAt(k) - 'a';
      int j = search(d[c], i);
      if (j == d[c].size()) {
        return false;
      }
      i = d[c].get(j);
    }
    return true;
  }

  private int search(List<Integer> t, int x) {
    int left = 0, right = t.size();
    while (left < right) {
      int mid = (left + right) >> 1;
      if (t.get(mid) > x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

class Solution {
public:
  int numMatchingSubseq(string s, vector<string>& words) {
    vector<vector<int>> d(26);
    for (int i = 0; i < s.size(); ++i) d[s[i] - 'a'].emplace_back(i);
    int ans = 0;
    auto check = [&](string& w) {
      int i = -1;
      for (char& c : w) {
        auto& t = d[c - 'a'];
        int j = upper_bound(t.begin(), t.end(), i) - t.begin();
        if (j == t.size()) return false;
        i = t[j];
      }
      return true;
    };
    for (auto& w : words) ans += check(w);
    return ans;
  }
};

func numMatchingSubseq(s string, words []string) (ans int) {
  d := [26][]int{}
  for i, c := range s {
    d[c-'a'] = append(d[c-'a'], i)
  }
  check := func(w string) bool {
    i := -1
    for _, c := range w {
      t := d[c-'a']
      j := sort.SearchInts(t, i+1)
      if j == len(t) {
        return false
      }
      i = t[j]
    }
    return true
  }
  for _, w := range words {
    if check(w) {
      ans++
    }
  }
  return
}