Skip to content

3292. Minimum Number of Valid Strings to Form Target II 👍

  • Time: $O(|\texttt{words}| \cdot \Sigma (|\texttt{words[i]}| + |\texttt{target}|))$
  • Space: $O(|\texttt{words}| \cdot \Sigma (|\texttt{words[i]}| + |\texttt{target}|))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
 public:
  // 3291. Minimum Number of Valid Strings to Form Target I
  int minValidStrings(vector<string>& words, string target) {
    int ans = 0;
    int unmatchedPrefix = target.length();
    vector<vector<int>> lpsList;

    for (const string& word : words)
      lpsList.push_back(getLPS(word + '#' + target));

    while (unmatchedPrefix > 0) {
      // Greedily choose the word that has the longest suffix match with the
      // remaining unmatched prefix.
      int maxMatchSuffix = 0;
      for (int i = 0; i < words.size(); ++i)
        maxMatchSuffix = max(maxMatchSuffix,
                             lpsList[i][words[i].length() + unmatchedPrefix]);
      if (maxMatchSuffix == 0)
        return -1;
      ++ans;
      unmatchedPrefix -= maxMatchSuffix;
    }

    return ans;
  }

 private:
  // Returns the lps array, where lps[i] is the length of the longest prefix of
  // pattern[0..i] which is also a suffix of this substring.
  vector<int> getLPS(const string& pattern) {
    vector<int> lps(pattern.length());
    for (int i = 1, j = 0; i < pattern.length(); ++i) {
      while (j > 0 && pattern[j] != pattern[i])
        j = lps[j - 1];
      if (pattern[i] == pattern[j])
        lps[i] = ++j;
    }
    return lps;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
  // 3291. Minimum Number of Valid Strings to Form Target I
  public int minValidStrings(String[] words, String target) {
    int ans = 0;
    int unmatchedPrefix = target.length();
    int[][] lpsList = new int[words.length][];

    for (int i = 0; i < words.length; ++i)
      lpsList[i] = getLPS(words[i] + '#' + target);

    while (unmatchedPrefix > 0) {
      // Greedily choose the word that has the longest suffix match with the
      // remaining unmatched prefix.
      int maxMatchSuffix = 0;
      for (int i = 0; i < words.length; ++i)
        maxMatchSuffix = Math.max(maxMatchSuffix, lpsList[i][words[i].length() + unmatchedPrefix]);
      if (maxMatchSuffix == 0)
        return -1;
      ++ans;
      unmatchedPrefix -= maxMatchSuffix;
    }

    return ans;
  }

  // Returns the lps array, where lps[i] is the length of the longest prefix of
  // pattern[0..i] which is also a suffix of this substring.
  private int[] getLPS(final String pattern) {
    int[] lps = new int[pattern.length()];
    for (int i = 1, j = 0; i < pattern.length(); ++i) {
      while (j > 0 && pattern.charAt(j) != pattern.charAt(i))
        j = lps[j - 1];
      if (pattern.charAt(i) == pattern.charAt(j))
        lps[i] = ++j;
    }
    return lps;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
  # 3291. Minimum Number of Valid Strings to Form Target I
  def minValidStrings(self, words: list[str], target: str) -> int:
    ans = 0
    unmatchedPrefix = len(target)
    lpsList = [self._getLPS(word + '#' + target) for word in words]

    while unmatchedPrefix > 0:
      # Greedily choose the word that has the longest suffix match with the
      # remaining unmatched prefix.
      maxMatchSuffix = 0
      for lps, word in zip(lpsList, words):
        maxMatchSuffix = max(maxMatchSuffix, lps[len(word) + unmatchedPrefix])
      if maxMatchSuffix == 0:
        return -1
      ans += 1
      unmatchedPrefix -= maxMatchSuffix

    return ans

  def _getLPS(self, pattern: str) -> list[int]:
    """
    Returns the lps array, where lps[i] is the length of the longest prefix of
    pattern[0..i] which is also a suffix of this substring.
    """
    lps = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
      while j > 0 and pattern[j] != pattern[i]:
        j = lps[j - 1]
      if pattern[i] == pattern[j]:
        lps[i] = j + 1
        j += 1
    return lps