3291. Minimum Number of Valid Strings to Form Target I

MediumTrieSegment TreeArrayStringBinary SearchDynamic ProgrammingString MatchingHash FunctionRolling Hash

Problem Description

You are provided with an array of strings words and a target string target. A string x is considered valid if it is a prefix of any string within the words array. The task is to return the minimum number of valid strings that can be concatenated to form the target. If forming target is not feasible, return -1.

Intuition

To solve this problem, we can use a combination of a Trie data structure and memoization. The idea is to first store all the valid prefixes in the Trie. By doing this, we can efficiently check which parts of the target can be formed using valid prefixes from words.

The main challenge is to determine the minimum number of valid prefixes needed to form the target. We can achieve this by defining a recursive function dfs(i), which computes the minimum number of strings required to form the substring starting from the i-th character of target.

Begin at the start of target and attempt to find valid prefixes that match the start of the substring.
For each valid prefix found, compute recursively the minimum number of strings needed for the rest of the string (the part not covered by the current prefix).
Use memoization to store already computed results for specific starting positions to avoid recalculating, thus optimizing the solution.

This approach provides an efficient way to tackle the problem by leveraging the Trie structure for quick prefix checks and using dynamic programming principles to minimize computations through memoization.

Learn more about Trie, Segment Tree, Binary Search and Dynamic Programming patterns.

Solution Approach

The solution leverages a combination of Trie data structure and memoization to efficiently determine the minimum number of valid strings needed to form the target string.

First, let's outline the solution approach:

Trie Construction:
- We start by constructing a Trie from the words array. Each string in words is inserted into the Trie, where each character represents a node. This allows us to quickly check if a prefix of the target is valid.
Memoization with Depth-First Search (DFS):
- We define a recursive function dfs(i) which returns the minimum number of valid strings required to concatenate the substring of target starting at index i.
- The function works as follows:
  - If i is beyond the length of target, return 0 because no more strings are needed.
  - Otherwise, initialize an infinite answer ans.
  - Use a node pointer starting from the root of the Trie. For each character target[j] starting from index i, check if this character exists in the current Trie node's children.
  - If it exists, move the Trie node to this child and continue; if not, break the loop as no further matching prefix exists.
  - Each time a valid ending is reached in a Trie path, recursively compute 1 + dfs(j + 1) and update ans with the minimum value.
  - Memoize the result for dfs(i) to avoid redundant calculations.
Final Computation:
- Compute the result by calling dfs(0), which processes the whole target string.
- If the result is less than infinity, return it; otherwise, return -1 indicating target can't be formed using valid strings.

The solution efficiently determines the minimum number of strings needed by combining the efficient prefix-check capabilities of a Trie with the minimized recomputation achieved through memoization.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider an example where the words array is ["ab", "abc", "cd", "def", "abcd"] and the target string is "abcdef".

Step 1: Construct the Trie

Insert each string from words into the Trie. The Trie will help in quickly checking whether prefixes of target exist in words.

The Trie structure would look something like this:

      root
      ├── a
      │   ├── b
      │   │   ├── c (end) 
      │   │   └── (end)
      │   └── c
      │       └── d (end)
      ├── c
      │   └── d (end)
      └── d
          └── e
              └── f (end)

Step 2: Depth-First Search with Memoization

Define dfs(i) to find the minimum number of valid strings starting from index i in target.
Compute dfs(0):
- Start with the root of the Trie and target[0] = 'a'.
- Move to the child node a and continue.
Compute valid chunks starting from a:
- ab is a valid prefix. Continue with dfs(2) for target[2:] = "cdef".
- abc is also a valid prefix. Continue with dfs(3) for target[3:] = "def".
- abcd is valid too. Continue with dfs(4) for target[4:] = "ef".
Recursion:
- dfs(2) checks if "cd" is a valid prefix in the remaining string "cdef". It is, hence compute dfs(4) for target[4:] = "ef" again.
- dfs(3) requires "def", which is valid. As it matches exactly, dfs(6) returns 0.
Compute dfs(4):
- Begin with the Trie root and target[4] = 'e'. No valid prefix starts with 'e', so return infinity.
- However, in further recursive calls, reaching "def" validates using one more valid string, which completes target.
Combine results:
- dfs(0): minimum(1 + dfs(2), 1 + dfs(3), 1 + dfs(4))
- Simplified into valid paths: [1 + 1 + 0, 1 + 0]
Thus, the minimum number of valid strings needed is 2 ("abc" and "def").

Final Result:

Call dfs(0), which constructs "abcdef" using a minimum of 2 valid strings from words.
The function thus returns 2.

Hence, the target "abcdef" can be formed by concatenating the minimum of two valid prefixes: "abc" and "def".

Solution Implementation

1from typing import List, Optional
2from functools import cache
3from math import inf
4
5# Utility function to return the minimum of two values
6def min(a: int, b: int) -> int:
7    return a if a < b else b
8
9
10class Trie:
11    def __init__(self):
12        # Initialize each trie node with a list for its children (26 alphabet letters)
13        self.children: List[Optional[Trie]] = [None] * 26
14
15    def insert(self, w: str):
16        # Insert a word into the trie
17        node = self
18        # Convert each character into an index (0-25) and walk through the trie
19        for i in map(lambda c: ord(c) - ord('a'), w):
20            if node.children[i] is None:
21                # If the path doesn't exist, create a new node
22                node.children[i] = Trie()
23            # Move to the child node
24            node = node.children[i]
25
26
27class Solution:
28    def minValidStrings(self, words: List[str], target: str) -> int:
29        # Depth-first search helper function with memoization
30        @cache
31        def dfs(i: int) -> int:
32            if i >= n:
33                # If at or beyond end of the target, no more substrings needed
34                return 0
35            node = trie
36            ans = inf
37            # Try to create a new substring starting from index i
38            for j in range(i, n):
39                k = ord(target[j]) - ord('a')  # Index of character
40                if node.children[k] is None:
41                    # If the path doesn't exist in the trie, break the loop
42                    break
43                # Move to the next node in the trie
44                node = node.children[k]
45                # Recur for the remaining substring and update the answer
46                ans = min(ans, 1 + dfs(j + 1))
47            return ans
48
49        # Create a trie and insert each word from the list
50        trie = Trie()
51        for w in words:
52            trie.insert(w)
53        n = len(target)
54        # Start DFS from index 0
55        ans = dfs(0)
56        # Return the minimum number of substrings if found, otherwise return -1
57        return ans if ans < inf else -1
58

1class TrieNode {
2    TrieNode[] children = new TrieNode[26]; // Array to store children nodes for each character from 'a' to 'z'
3
4    void insert(String word) {
5        TrieNode node = this;
6        for (int i = 0; i < word.length(); ++i) {
7            int index = word.charAt(i) - 'a'; // Calculate index of the character
8            if (node.children[index] == null) {
9                node.children[index] = new TrieNode(); // Create a new TrieNode if it does not exist
10            }
11            node = node.children[index]; // Move to the corresponding child node
12        }
13    }
14}
15
16class Solution {
17    private Integer[] minimumSteps; // Memoization array for storing minimum steps to make valid words from index i
18    private char[] targetChars; // Array representing the target string
19    private TrieNode trieRoot; // Root of the Trie
20    private final int INF = 1 << 30; // A large constant value representing infinity
21
22    public int minValidStrings(String[] words, String target) {
23        trieRoot = new TrieNode();
24      
25        // Insert each word into the Trie
26        for (String word : words) {
27            trieRoot.insert(word);
28        }
29      
30        // Convert target string to character array for easy access
31        targetChars = target.toCharArray();
32      
33        // Initialize the memoization array with nulls
34        minimumSteps = new Integer[targetChars.length];
35      
36        // Get the minimum valid strings starting from index 0
37        int result = dfs(0);
38      
39        // Return result if valid otherwise -1
40        return result < INF ? result : -1;
41    }
42
43    private int dfs(int startIndex) {
44        // Base case: If startIndex reaches the end of targetChars, no more strings are needed
45        if (startIndex >= targetChars.length) {
46            return 0;
47        }
48      
49        // If already calculated, return the stored result
50        if (minimumSteps[startIndex] != null) {
51            return minimumSteps[startIndex];
52        }
53      
54        TrieNode currentNode = trieRoot;
55        minimumSteps[startIndex] = INF; // Initialize with infinity
56      
57        // Explore further down the Trie from the current startIndex
58        for (int endIndex = startIndex; endIndex < targetChars.length; ++endIndex) {
59            int charIndex = targetChars[endIndex] - 'a'; // Get character's index
60          
61            // If no valid continuation in the Trie, break
62            if (currentNode.children[charIndex] == null) {
63                break;
64            }
65          
66            // Try forming a valid word from startIndex to endIndex
67            minimumSteps[startIndex] = Math.min(minimumSteps[startIndex], 1 + dfs(endIndex + 1));
68            currentNode = currentNode.children[charIndex]; // Move to the child node
69        }
70      
71        return minimumSteps[startIndex];
72    }
73}
74

1#include <vector>
2#include <string>
3#include <cstring>
4#include <algorithm>
5
6using namespace std;
7
8// Trie node definition
9class Trie {
10public:
11    Trie* children[26]{};  // Pointers to child nodes for each letter (a-z)
12
13    // Insert word into the trie
14    void insert(string& word) {
15        Trie* node = this;
16        for (char& c : word) {
17            int index = c - 'a';  // Calculate index for the character
18            if (!node->children[index]) {
19                node->children[index] = new Trie(); // Create a new node if it doesn't exist
20            }
21            node = node->children[index];  // Move to the child node
22        }
23    }
24};
25
26class Solution {
27public:
28    int minValidStrings(vector<string>& words, string target) {
29        int n = target.size();
30        Trie* trie = new Trie();
31      
32        // Insert each word into the trie
33        for (auto& word : words) {
34            trie->insert(word);
35        }
36      
37        const int inf = 1 << 30;  // Large number to represent infinity
38        int f[n];  // Array to store results for substrings of 'target'
39        memset(f, -1, sizeof(f));  // Initialize all entries to -1
40
41        // Define a recursive depth-first search function with lambda
42        auto dfs = [&](auto&& dfs, int i) -> int {
43            if (i >= n) {
44                return 0; // Base case: If we've processed the entire target, return 0
45            }
46            if (f[i] != -1) {
47                return f[i];  // Use cached result if already computed
48            }
49          
50            f[i] = inf;  // Initialize with infinity, as we're searching for the minimum
51            Trie* node = trie;  // Start from the root of the trie
52            for (int j = i; j < n; ++j) {
53                int index = target[j] - 'a';  // Calculate index for the current character
54                if (!node->children[index]) {
55                    break;  // If no further path in the trie, break the loop
56                }
57                node = node->children[index];  // Move to the corresponding child node
58                // Choose min between current and 1 + result of dfs from next index
59                f[i] = min(f[i], 1 + dfs(dfs, j + 1));
60            }
61            return f[i];  // Return the computed result
62        };
63
64        int ans = dfs(dfs, 0);  // Start DFS from the first character of target
65        return ans < inf ? ans : -1;  // If result is still infinity, no valid solution found
66    }
67};
68

1// A trie node structure with an array of children initialized to null
2const createTrieNode = (): (Trie | null)[] => Array(26).fill(null);
3
4// Insert a word into the trie
5function insert(word: string, trie: (Trie | null)[]): void {
6    let node: (Trie | null)[] = trie;
7    for (const c of word) {
8        const index = c.charCodeAt(0) - 'a'.charCodeAt(0);
9        if (!node[index]) {
10            node[index] = createTrieNode();
11        }
12        node = node[index]!;
13    }
14}
15
16// Calculate the minimum number of strings required from the provided list
17function minValidStrings(words: string[], target: string): number {
18    const n = target.length;
19    const trie: (Trie | null)[] = createTrieNode();
20
21    // Insert every word into the trie
22    for (const word of words) {
23        insert(word, trie);
24    }
25
26    // Set what represents infinity for unreachable positions
27    const inf = 1 << 30;
28  
29    // Memoization array to store the smallest number of strings needed
30    const memo = Array(n).fill(0);
31
32    // Helper function using DFS for dynamic calculation
33    const dfs = (index: number): number => {
34        // If past the end of target, no more words are needed
35        if (index >= n) {
36            return 0;
37        }
38      
39        // If already computed, return stored result
40        if (memo[index]) {
41            return memo[index];
42        }
43      
44        // Default result to infinity for comparison
45        memo[index] = inf;
46        let node: (Trie | null)[] | null = trie;
47      
48        // Traverse target character by character
49        for (let j = index; j < n; ++j) {
50            const letterIndex = target[j].charCodeAt(0) - 'a'.charCodeAt(0);
51            if (!node?.[letterIndex]) {
52                break; // Break if no more words match in the trie
53            }
54            node = node[letterIndex];
55          
56            // Calculate number of words needed with this word chosen
57            memo[index] = Math.min(memo[index], 1 + dfs(j + 1));
58        }
59      
60        return memo[index];
61    };
62
63    // Start DFS from the beginning of the target string
64    const result = dfs(0);
65  
66    // Check if a valid solution was found
67    return result < inf ? result : -1;
68}
69

Time and Space Complexity

The time complexity of the given code is O(n^2 + L). This is because the dfs function explores all possible substring partitions of the target string and makes recursive calls for each position i in the target, leading to a complexity of O(n^2). The Trie insertion for all words contributes O(L), where L is the total length of all words. Therefore, the overall time complexity is O(n^2 + L).

The space complexity is O(n + L). This accounts for the space used by the recursion stack, which is O(n), as well as the space used by the Trie structure for storing the words, which is O(L). Hence, the total space complexity is O(n + L).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don’t know