Skip to content

3291. Minimum Number of Valid Strings to Form Target I

SourceWeekly Contest 415 Q3DifficultyMediumRating2081

Description

You are given an array of strings words and a string target.

A string x is called valid if x is a prefix of any string in words.

Return the minimum number of valid strings that can be concatenated to form target. If it is not possible to form target, return -1.

 

Example 1:

Input: words = ["abc","aaaaa","bcdef"], target = "aabcdabc"

Output: 3

Explanation:

The target string can be formed by concatenating:

  • Prefix of length 2 of words[1], i.e. "aa".
  • Prefix of length 3 of words[2], i.e. "bcd".
  • Prefix of length 3 of words[0], i.e. "abc".

Example 2:

Input: words = ["abababab","ab"], target = "ababaababa"

Output: 2

Explanation:

The target string can be formed by concatenating:

  • Prefix of length 5 of words[0], i.e. "ababa".
  • Prefix of length 5 of words[0], i.e. "ababa".

Example 3:

Input: words = ["abcdef"], target = "xyz"

Output: -1

 

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 5 * 103
  • The input is generated such that sum(words[i].length) <= 105.
  • words[i] consists only of lowercase English letters.
  • 1 <= target.length <= 5 * 103
  • target consists only of lowercase English letters.

Solutions

Solution 1: Trie + Memoization

Thinking

Concatenate prefixes of \(\textit{words}\) to form \(\textit{target}\) with as few pieces as possible. \(|target|\le 5\times 10^3\) and total word length \(10^5\); trying every word at every index repeats prefixes.

Store every word in a trie. From \(i\), walk \(\textit{target}\) down the trie; each existing node is a cut, plus \(\textit{dfs}(j+1)\). After memoization each start walks at most \(O(n)\).

We can use a trie to store all valid strings and then use memoization to calculate the answer.

We design a function \(\textit{dfs}(i)\), which represents the minimum number of strings needed to concatenate starting from the \(i\)-th character of the string \(\textit{target}\). The answer is \(\textit{dfs}(0)\).

The function \(\textit{dfs}(i)\) is calculated as follows:

  • If \(i \geq n\), it means the string \(\textit{target}\) has been completely traversed, so we return \(0\);
  • Otherwise, we can find valid strings in the trie that start with \(\textit{target}[i]\), and then recursively calculate \(\textit{dfs}(i + \text{len}(w))\), where \(w\) is the valid string found. We take the minimum of these values and add \(1\) as the return value of \(\textit{dfs}(i)\).

To avoid redundant calculations, we use memoization.

The time complexity is \(O(n^2 + L)\), and the space complexity is \(O(n + L)\). Here, \(n\) is the length of the string \(\textit{target}\), and \(L\) is the total length of all valid strings.

 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
def min(a: int, b: int) -> int:
    return a if a < b else b


class Trie:
    def __init__(self):
        self.children: List[Optional[Trie]] = [None] * 26

    def insert(self, w: str):
        node = self
        for i in map(lambda c: ord(c) - 97, w):
            if node.children[i] is None:
                node.children[i] = Trie()
            node = node.children[i]


class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= n:
                return 0
            node = trie
            ans = inf
            for j in range(i, n):
                k = ord(target[j]) - 97
                if node.children[k] is None:
                    break
                node = node.children[k]
                ans = min(ans, 1 + dfs(j + 1))
            return ans

        trie = Trie()
        for w in words:
            trie.insert(w)
        n = len(target)
        ans = dfs(0)
        return ans if ans < inf else -1

 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
42
43
44
45
46
47
48
49
50
51
52
class Trie {
    Trie[] children = new Trie[26];

    void insert(String w) {
        Trie node = this;
        for (int i = 0; i < w.length(); ++i) {
            int j = w.charAt(i) - 'a';
            if (node.children[j] == null) {
                node.children[j] = new Trie();
            }
            node = node.children[j];
        }
    }
}

class Solution {
    private Integer[] f;
    private char[] s;
    private Trie trie;
    private final int inf = 1 << 30;

    public int minValidStrings(String[] words, String target) {
        trie = new Trie();
        for (String w : words) {
            trie.insert(w);
        }
        s = target.toCharArray();
        f = new Integer[s.length];
        int ans = dfs(0);
        return ans < inf ? ans : -1;
    }

    private int dfs(int i) {
        if (i >= s.length) {
            return 0;
        }
        if (f[i] != null) {
            return f[i];
        }
        Trie node = trie;
        f[i] = inf;
        for (int j = i; j < s.length; ++j) {
            int k = s[j] - 'a';
            if (node.children[k] == null) {
                break;
            }
            f[i] = Math.min(f[i], 1 + dfs(j + 1));
            node = node.children[k];
        }
        return f[i];
    }
}

 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
42
43
44
45
46
47
48
49
50
class Trie {
public:
    Trie* children[26]{};

    void insert(string& word) {
        Trie* node = this;
        for (char& c : word) {
            int i = c - 'a';
            if (!node->children[i]) {
                node->children[i] = new Trie();
            }
            node = node->children[i];
        }
    }
};

class Solution {
public:
    int minValidStrings(vector<string>& words, string target) {
        int n = target.size();
        Trie* trie = new Trie();
        for (auto& w : words) {
            trie->insert(w);
        }
        const int inf = 1 << 30;
        int f[n];
        memset(f, -1, sizeof(f));
        auto dfs = [&](this auto&& dfs, int i) -> int {
            if (i >= n) {
                return 0;
            }
            if (f[i] != -1) {
                return f[i];
            }
            f[i] = inf;
            Trie* node = trie;
            for (int j = i; j < n; ++j) {
                int k = target[j] - 'a';
                if (!node->children[k]) {
                    break;
                }
                node = node->children[k];
                f[i] = min(f[i], 1 + dfs(j + 1));
            }
            return f[i];
        };
        int ans = dfs(0);
        return ans < inf ? ans : -1;
    }
};

 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
42
43
44
45
46
47
48
type Trie struct {
    children [26]*Trie
}

func (t *Trie) insert(word string) {
    node := t
    for _, c := range word {
        idx := c - 'a'
        if node.children[idx] == nil {
            node.children[idx] = &Trie{}
        }
        node = node.children[idx]
    }
}

func minValidStrings(words []string, target string) int {
    n := len(target)
    trie := &Trie{}
    for _, w := range words {
        trie.insert(w)
    }
    const inf int = 1 << 30
    f := make([]int, n)
    var dfs func(int) int
    dfs = func(i int) int {
        if i >= n {
            return 0
        }
        if f[i] != 0 {
            return f[i]
        }
        node := trie
        f[i] = inf
        for j := i; j < n; j++ {
            k := int(target[j] - 'a')
            if node.children[k] == nil {
                break
            }
            f[i] = min(f[i], 1+dfs(j+1))
            node = node.children[k]
        }
        return f[i]
    }
    if ans := dfs(0); ans < inf {
        return ans
    }
    return -1
}

 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
42
43
44
45
46
47
class Trie {
    children: (Trie | null)[] = Array(26).fill(null);

    insert(word: string): void {
        let node: Trie = this;
        for (const c of word) {
            const i = c.charCodeAt(0) - 'a'.charCodeAt(0);
            if (!node.children[i]) {
                node.children[i] = new Trie();
            }
            node = node.children[i];
        }
    }
}

function minValidStrings(words: string[], target: string): number {
    const n = target.length;
    const trie = new Trie();
    for (const w of words) {
        trie.insert(w);
    }
    const inf = 1 << 30;
    const f = Array(n).fill(0);

    const dfs = (i: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i]) {
            return f[i];
        }
        f[i] = inf;
        let node: Trie | null = trie;
        for (let j = i; j < n; ++j) {
            const k = target[j].charCodeAt(0) - 'a'.charCodeAt(0);
            if (!node?.children[k]) {
                break;
            }
            node = node.children[k];
            f[i] = Math.min(f[i], 1 + dfs(j + 1));
        }
        return f[i];
    };

    const ans = dfs(0);
    return ans < inf ? ans : -1;
}

Solution 2: Trie + Dynamic Programming

Thinking

Trying every word at every index repeats prefixes. \(|target|\) can reach \(5\times 10^3\), and whenever \(\textit{target}[i]\) is the first letter of some word the first call always lands on \(i+1\), so the chain has depth \(n\). A piece must be a prefix of some word, so the fewest pieces from \(i\) depend only on later indices. Store the words in a trie, set \(f[n]=0\), and fill \(i\) from \(n-1\) down to \(0\): walk \(\textit{target}\) down the trie and update \(f[i]\) with \(1+f[j+1]\) at every existing node. If \(f[0]\) is still at least the sentinel, return \(-1\).

We store every string in \(\textit{words}\) in a trie. Let \(f[i]\) be the minimum number of strings needed starting from index \(i\) of \(\textit{target}\), with \(f[n] = 0\). The answer is \(f[0]\).

Scan \(i\) from \(n - 1\) down to \(0\). Starting from the trie root, walk down \(\textit{target}[i..]\). Each time the walk enters an existing node, that prefix is a valid string, and we update \(f[i]\) with \(1 + f[j + 1]\).

If \(f[0]\) is at least the preset upper bound, \(\textit{target}\) cannot be formed and we return \(-1\). Otherwise we return \(f[0]\).

The time complexity is \(O(n^2 + L)\), and the space complexity is \(O(n + L)\). Here, \(n\) is the length of \(\textit{target}\), and \(L\) is the total length of all valid strings.

 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
class Trie:
    def __init__(self):
        self.children: List[Optional[Trie]] = [None] * 26

    def insert(self, w: str):
        node = self
        for i in map(lambda c: ord(c) - 97, w):
            if node.children[i] is None:
                node.children[i] = Trie()
            node = node.children[i]


class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        trie = Trie()
        for w in words:
            trie.insert(w)
        n = len(target)
        f = [inf] * (n + 1)
        f[n] = 0
        for i in range(n - 1, -1, -1):
            node = trie
            for j in range(i, n):
                k = ord(target[j]) - 97
                if node.children[k] is None:
                    break
                node = node.children[k]
                f[i] = min(f[i], 1 + f[j + 1])
        return f[0] if f[0] < inf else -1

 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
42
class Trie {
    Trie[] children = new Trie[26];

    void insert(String w) {
        Trie node = this;
        for (int i = 0; i < w.length(); ++i) {
            int j = w.charAt(i) - 'a';
            if (node.children[j] == null) {
                node.children[j] = new Trie();
            }
            node = node.children[j];
        }
    }
}

class Solution {
    public int minValidStrings(String[] words, String target) {
        Trie trie = new Trie();
        for (String w : words) {
            trie.insert(w);
        }
        int n = target.length();
        int inf = 1 << 30;
        int[] f = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            f[i] = inf;
        }
        char[] s = target.toCharArray();
        for (int i = n - 1; i >= 0; --i) {
            Trie node = trie;
            for (int j = i; j < n; ++j) {
                int k = s[j] - 'a';
                if (node.children[k] == null) {
                    break;
                }
                node = node.children[k];
                f[i] = Math.min(f[i], 1 + f[j + 1]);
            }
        }
        return f[0] < inf ? f[0] : -1;
    }
}

 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 Trie {
public:
    Trie* children[26]{};

    void insert(string& word) {
        Trie* node = this;
        for (char& c : word) {
            int i = c - 'a';
            if (!node->children[i]) {
                node->children[i] = new Trie();
            }
            node = node->children[i];
        }
    }
};

class Solution {
public:
    int minValidStrings(vector<string>& words, string target) {
        int n = target.size();
        Trie* trie = new Trie();
        for (auto& w : words) {
            trie->insert(w);
        }
        const int inf = 1 << 30;
        vector<int> f(n + 1, inf);
        f[n] = 0;
        for (int i = n - 1; i >= 0; --i) {
            Trie* node = trie;
            for (int j = i; j < n; ++j) {
                int k = target[j] - 'a';
                if (!node->children[k]) {
                    break;
                }
                node = node->children[k];
                f[i] = min(f[i], 1 + f[j + 1]);
            }
        }
        return f[0] < inf ? f[0] : -1;
    }
};

 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
42
type Trie struct {
    children [26]*Trie
}

func (t *Trie) insert(word string) {
    node := t
    for _, c := range word {
        idx := c - 'a'
        if node.children[idx] == nil {
            node.children[idx] = &Trie{}
        }
        node = node.children[idx]
    }
}

func minValidStrings(words []string, target string) int {
    n := len(target)
    trie := &Trie{}
    for _, w := range words {
        trie.insert(w)
    }
    const inf int = 1 << 30
    f := make([]int, n+1)
    for i := 0; i < n; i++ {
        f[i] = inf
    }
    for i := n - 1; i >= 0; i-- {
        node := trie
        for j := i; j < n; j++ {
            k := int(target[j] - 'a')
            if node.children[k] == nil {
                break
            }
            node = node.children[k]
            f[i] = min(f[i], 1+f[j+1])
        }
    }
    if f[0] < inf {
        return f[0]
    }
    return -1
}

 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
class Trie {
    children: (Trie | null)[] = Array(26).fill(null);

    insert(word: string): void {
        let node: Trie = this;
        for (const c of word) {
            const i = c.charCodeAt(0) - 'a'.charCodeAt(0);
            if (!node.children[i]) {
                node.children[i] = new Trie();
            }
            node = node.children[i];
        }
    }
}

function minValidStrings(words: string[], target: string): number {
    const n = target.length;
    const trie = new Trie();
    for (const w of words) {
        trie.insert(w);
    }
    const inf = 1 << 30;
    const f: number[] = Array(n + 1).fill(inf);
    f[n] = 0;
    for (let i = n - 1; i >= 0; --i) {
        let node: Trie | null = trie;
        for (let j = i; j < n; ++j) {
            const k = target.charCodeAt(j) - 97;
            if (!node?.children[k]) {
                break;
            }
            node = node.children[k];
            f[i] = Math.min(f[i], 1 + f[j + 1]);
        }
    }
    return f[0] < inf ? f[0] : -1;
}

Comments