Skip to content

3253. Construct String with Minimum Cost (Easy) πŸ”’

DifficultyMedium

Description

You are given a string target, an array of strings words, and an integer array costs, both arrays of the same length.

Imagine an empty string s.

You can perform the following operation any number of times (including zero):

  • Choose an index i in the range [0, words.length - 1].
  • Append words[i] to s.
  • The cost of operation is costs[i].

Return the minimum cost to make s equal to target. If it's not possible, return -1.

 

Example 1:

Input: target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]

Output: 7

Explanation:

The minimum cost can be achieved by performing the following operations:

  • Select index 1 and append "abc" to s at a cost of 1, resulting in s = "abc".
  • Select index 2 and append "d" to s at a cost of 1, resulting in s = "abcd".
  • Select index 4 and append "ef" to s at a cost of 5, resulting in s = "abcdef".

Example 2:

Input: target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]

Output: -1

Explanation:

It is impossible to make s equal to target, so we return -1.

 

Constraints:

  • 1 <= target.length <= 2000
  • 1 <= words.length == costs.length <= 50
  • 1 <= words[i].length <= target.length
  • target and words[i] consist only of lowercase English letters.
  • 1 <= costs[i] <= 105

Solutions

Thinking

\(\textit{target}\) has length \(2000\) and there are at most \(50\) words, so matching every word at every index would pass, but shared prefixes would be compared repeatedly. A trie lets one walk from \(i\) produce every match end.

\(\textit{dfs}(i)\) is the cheapest way to build \(\textit{target}[i:]\). Walking the trie to a node that stores a cost adds \(\textit{dfs}(j+1)\). After memoization there are \(n\) states, each walking \(O(n)\).

We first create a Trie \(\textit{trie}\), where each node in the Trie contains an array \(\textit{children}\) of length \(26\), and each element in the array is a pointer to the next node. Each node in the Trie also contains a \(\textit{cost}\) variable, which represents the minimum cost from the root node to the current node.

We traverse the \(\textit{words}\) array, inserting each word into the Trie while updating the \(\textit{cost}\) variable for each node.

Next, we define a memoized search function \(\textit{dfs}(i)\), which represents the minimum cost to construct the string starting from \(\textit{target}[i]\). The answer is \(\textit{dfs}(0)\).

The calculation process of the function \(\textit{dfs}(i)\) is as follows:

  • If \(i \geq \textit{len}(\textit{target})\), it means the entire string has been constructed, so return \(0\).
  • Otherwise, we start from the root node of the \(\textit{trie}\) and traverse all suffixes starting from \(\textit{target}[i]\), finding the minimum cost, which is the \(\textit{cost}\) variable in the \(\textit{trie}\), plus the result of \(\textit{dfs}(j+1)\), where \(j\) is the ending position of the suffix starting from \(\textit{target}[i]\).

Finally, if \(\textit{dfs}(0) < \textit{inf}\), return \(\textit{dfs}(0)\); otherwise, return \(-1\).

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 sum of the lengths of all words in the \(\textit{words}\) array.

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

    def insert(self, word: str, cost: int):
        node = self
        for c in word:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.cost = min(node.cost, cost)


class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(target):
                return 0
            ans = inf
            node = trie
            for j in range(i, len(target)):
                idx = ord(target[j]) - ord("a")
                if node.children[idx] is None:
                    return ans
                node = node.children[idx]
                ans = min(ans, node.cost + dfs(j + 1))
            return ans

        trie = Trie()
        for word, cost in zip(words, costs):
            trie.insert(word, cost)
        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
53
class Trie {
    public final int inf = 1 << 29;
    public Trie[] children = new Trie[26];
    public int cost = inf;

    public void insert(String word, int cost) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx];
        }
        node.cost = Math.min(node.cost, cost);
    }
}

class Solution {
    private Trie trie = new Trie();
    private char[] target;
    private Integer[] f;

    public int minimumCost(String target, String[] words, int[] costs) {
        for (int i = 0; i < words.length; ++i) {
            trie.insert(words[i], costs[i]);
        }
        this.target = target.toCharArray();
        f = new Integer[target.length()];
        int ans = dfs(0);
        return ans < trie.inf ? ans : -1;
    }

    private int dfs(int i) {
        if (i >= target.length) {
            return 0;
        }
        if (f[i] != null) {
            return f[i];
        }
        f[i] = trie.inf;
        Trie node = trie;
        for (int j = i; j < target.length; ++j) {
            int idx = target[j] - 'a';
            if (node.children[idx] == null) {
                return f[i];
            }
            node = node.children[idx];
            f[i] = Math.min(f[i], node.cost + dfs(j + 1));
        }
        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
51
52
53
const int inf = 1 << 29;

class Trie {
public:
    Trie* children[26]{};
    int cost = inf;

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

class Solution {
public:
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        Trie* trie = new Trie();
        for (int i = 0; i < words.size(); ++i) {
            trie->insert(words[i], costs[i]);
        }
        int n = target.length();
        int f[n];
        memset(f, 0, sizeof(f));
        auto dfs = [&](this auto&& dfs, int i) -> int {
            if (i >= n) {
                return 0;
            }
            if (f[i]) {
                return f[i];
            }
            f[i] = inf;
            Trie* node = trie;
            for (int j = i; j < n; ++j) {
                int idx = target[j] - 'a';
                if (!node->children[idx]) {
                    return f[i];
                }
                node = node->children[idx];
                f[i] = min(f[i], node->cost + 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
49
50
51
52
53
54
55
56
const inf = 1 << 29

type Trie struct {
    children [26]*Trie
    cost     int
}

func NewTrie() *Trie {
    return &Trie{cost: inf}
}

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

func minimumCost(target string, words []string, costs []int) int {
    trie := NewTrie()
    for i, word := range words {
        trie.insert(word, costs[i])
    }

    n := len(target)
    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]
        }
        f[i] = inf
        node := trie
        for j := i; j < n; j++ {
            idx := target[j] - 'a'
            if node.children[idx] == nil {
                return f[i]
            }
            node = node.children[idx]
            f[i] = min(f[i], node.cost+dfs(j+1))
        }
        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
48
49
50
51
52
53
54
55
const inf = 1 << 29;

class Trie {
    children: (Trie | null)[];
    cost: number;

    constructor() {
        this.children = Array(26).fill(null);
        this.cost = inf;
    }

    insert(word: string, cost: number): void {
        let node: Trie = this;
        for (const c of word) {
            const idx = c.charCodeAt(0) - 97;
            if (!node.children[idx]) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx]!;
        }
        node.cost = Math.min(node.cost, cost);
    }
}

function minimumCost(target: string, words: string[], costs: number[]): number {
    const trie = new Trie();
    for (let i = 0; i < words.length; ++i) {
        trie.insert(words[i], costs[i]);
    }

    const n = target.length;
    const f: number[] = 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 idx = target.charCodeAt(j) - 97;
            if (!node?.children[idx]) {
                return f[i];
            }
            node = node.children[idx];
            f[i] = Math.min(f[i], node!.cost + dfs(j + 1));
        }
        return f[i];
    };

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

Solution 2: Trie + Dynamic Programming

Thinking

Matching every word at every index repeats shared prefixes, so the words go into a trie and one walk lists every match end. \(\textit{target}\) has length \(2000\), and the walk calls the next index on the first character, so the search has depth \(n\). The minimum cost of suffix \(i\) depends only on later suffixes. Let \(f[i]\) be that cost, with \(f[n]=0\), and scan from the right, adding a node's \(\textit{cost}\) to \(f[j+1]\).

Insert every word into a trie. Each node stores \(\textit{children}\) for the next letters and a \(\textit{cost}\) equal to the cheapest word ending at that node, or infinity when no word ends there.

Let \(f[i]\) be the minimum cost of building \(\textit{target}\) from index \(i\), with \(f[n]=0\). For \(i\) from \(n-1\) down to \(0\), walk from the root along \(\textit{target}[i:]\). The walk stops when the next character has no child. Otherwise the node is reached and \(f[i]\) is updated with \(\textit{cost}+f[j+1]\). If \(f[0]\) is still infinite, return \(-1\); otherwise 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 sum of the lengths of all words in the \(\textit{words}\) array.

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

    def insert(self, word: str, cost: int):
        node = self
        for c in word:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.cost = min(node.cost, cost)


class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        trie = Trie()
        for word, cost in zip(words, costs):
            trie.insert(word, cost)
        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):
                idx = ord(target[j]) - ord("a")
                if node.children[idx] is None:
                    break
                node = node.children[idx]
                f[i] = min(f[i], node.cost + 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
43
class Trie {
    public final int inf = 1 << 29;
    public Trie[] children = new Trie[26];
    public int cost = inf;

    public void insert(String word, int cost) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx];
        }
        node.cost = Math.min(node.cost, cost);
    }
}

class Solution {
    public int minimumCost(String target, String[] words, int[] costs) {
        Trie trie = new Trie();
        for (int i = 0; i < words.length; ++i) {
            trie.insert(words[i], costs[i]);
        }
        int n = target.length();
        int inf = trie.inf;
        int[] f = new int[n + 1];
        Arrays.fill(f, inf);
        f[n] = 0;
        for (int i = n - 1; i >= 0; --i) {
            Trie node = trie;
            for (int j = i; j < n; ++j) {
                int idx = target.charAt(j) - 'a';
                if (node.children[idx] == null) {
                    break;
                }
                node = node.children[idx];
                f[i] = Math.min(f[i], node.cost + 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
43
44
const int inf = 1 << 29;

class Trie {
public:
    Trie* children[26]{};
    int cost = inf;

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

class Solution {
public:
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        Trie* trie = new Trie();
        for (int i = 0; i < words.size(); ++i) {
            trie->insert(words[i], costs[i]);
        }
        int n = target.length();
        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 idx = target[j] - 'a';
                if (!node->children[idx]) {
                    break;
                }
                node = node->children[idx];
                f[i] = min(f[i], node->cost + 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
43
44
45
46
47
48
49
const inf = 1 << 29

type Trie struct {
    children [26]*Trie
    cost     int
}

func NewTrie() *Trie {
    return &Trie{cost: inf}
}

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

func minimumCost(target string, words []string, costs []int) int {
    trie := NewTrie()
    for i, word := range words {
        trie.insert(word, costs[i])
    }
    n := len(target)
    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++ {
            idx := target[j] - 'a'
            if node.children[idx] == nil {
                break
            }
            node = node.children[idx]
            f[i] = min(f[i], node.cost+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
38
39
40
41
42
43
44
45
const inf = 1 << 29;

class Trie {
    children: (Trie | null)[];
    cost: number;

    constructor() {
        this.children = Array(26).fill(null);
        this.cost = inf;
    }

    insert(word: string, cost: number): void {
        let node: Trie = this;
        for (const c of word) {
            const idx = c.charCodeAt(0) - 97;
            if (!node.children[idx]) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx]!;
        }
        node.cost = Math.min(node.cost, cost);
    }
}

function minimumCost(target: string, words: string[], costs: number[]): number {
    const trie = new Trie();
    for (let i = 0; i < words.length; ++i) {
        trie.insert(words[i], costs[i]);
    }
    const n = target.length;
    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 idx = target.charCodeAt(j) - 97;
            if (!node?.children[idx]) {
                break;
            }
            node = node.children[idx];
            f[i] = Math.min(f[i], node!.cost + f[j + 1]);
        }
    }
    return f[0] < inf ? f[0] : -1;
}

Comments