Problem Description

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

A string x is considered valid if it is a prefix of at least one string in the words array. For example, if words = ["abc", "def"], then "a", "ab", "abc", "d", "de", and "def" are all valid strings, but "b", "ac", or "ef" are not valid.

Your task is to find the minimum number of valid strings that can be concatenated together to form the target string. The valid strings can be used multiple times and in any order.

If it's impossible to form the target string using valid strings, return -1.

For example:

• If words = ["abc", "def"] and target = "abcd", you could use "abc" (a valid prefix of "abc") and "d" (a valid prefix of "def") to form "abcd", requiring 2 valid strings.
• If words = ["abc"] and target = "def", it's impossible to form "def" using prefixes of "abc", so the answer would be -1.

The problem requires finding the optimal way to break down the target string into the fewest number of valid prefixes from the words array.

Intuition

The key insight is that we need to efficiently check if any substring starting from a position in target matches a prefix of any word in words. This immediately suggests using a Trie (prefix tree) data structure, which excels at prefix matching operations.

Think of the problem as trying to "cover" the entire target string using valid prefixes. At each position in target, we have choices - we can use any valid prefix that starts at that position. This creates overlapping subproblems, which hints at a dynamic programming approach.

Consider how we'd solve this step by step:

1. Starting from position i in target, we need to find all possible valid prefixes that match
2. For each valid prefix of length len, we jump to position i + len and solve the subproblem from there
3. We want the minimum among all these choices

The challenge is that checking all possible substrings against all words would be inefficient. This is where the Trie shines - by storing all words in a Trie, we can traverse it character by character while simultaneously traversing the target string. As soon as we can't find the next character in the Trie, we know there are no more valid prefixes from that starting position.

The recursive nature of the problem becomes clear: dfs(i) = minimum number of valid strings needed to form target[i:]. For each valid prefix found starting at position i, we recursively solve for the remaining substring. Since we might revisit the same positions multiple times through different paths, memoization prevents redundant calculations, transforming our solution into an efficient dynamic programming approach.

The combination of Trie for efficient prefix matching and memoized recursion for optimal substructure gives us an elegant solution to this string segmentation problem.

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

Solution Approach

The solution uses a Trie data structure combined with memoized recursion to efficiently find the minimum number of valid strings needed.

Trie Implementation

First, we build a Trie to store all words from the words array:

class [Trie](/problems/trie_intro):
    def __init__(self):
        self.children: List[Optional[Trie]] = [None] * 26  # 26 lowercase letters
  
    def insert(self, w: str):
        node = self
        for i in map(lambda c: ord(c) - 97, w):  # Convert 'a'-'z' to 0-25
            if node.children[i] is None:
                node.children[i] = Trie()
            node = node.children[i]

The Trie allows us to efficiently check if a substring of target matches any prefix of words in words.

Dynamic Programming with Memoization

The core algorithm uses a recursive function dfs(i) that returns the minimum number of valid strings needed to form target[i:] (the substring from index i to the end):

@cache
def dfs(i: int) -> int:
    if i >= n:  # Base case: reached end of target
        return 0
  
    node = [trie](/problems/trie_intro)
    ans = inf
  
    # Try all possible prefixes starting from position i
    for j in range(i, n):
        k = ord(target[j]) - 97  # Convert character to index
        if node.children[k] is None:
            break  # No more valid prefixes from this position
      
        node = node.children[k]
        ans = min(ans, 1 + dfs(j + 1))  # Use this prefix and recurse
  
    return ans

Algorithm Flow

1. Build the Trie: Insert all words from words into the Trie structure.

2. Start recursion: Call dfs(0) to find the minimum number of strings needed starting from index 0.

3. At each position i:

   • Try to match prefixes starting from target[i]
   • Traverse the Trie character by character
   • For each valid prefix found (ending at position j), recursively solve for dfs(j + 1)
   • Take the minimum among all valid choices and add 1 (for the current prefix used)

4. Memoization: The @cache decorator automatically memorizes results for each position i, preventing redundant calculations when the same position is reached through different paths.

5. Return result: If dfs(0) < inf, return it; otherwise return -1 (impossible to form target).

Time and Space Complexity

• Time: O(n²) in the worst case, where n is the length of target. For each starting position, we might check up to n characters.
• Space: O(m × k + n) where m is the total number of characters in all words (for the Trie), k is the average word length, and n for the memoization cache.

The elegance of this solution lies in combining the Trie's prefix-matching capability with dynamic programming's ability to solve overlapping subproblems efficiently.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• words = ["ab", "abc", "cd", "def"]
• target = "abcd"

Step 1: Build the Trie

We insert all words into the Trie structure:

        root
       /    \
      a      c      d
     /       |      |
    b        d      e
   /                |
  c                 f

Step 2: Start DFS from position 0

Call dfs(0) to find minimum strings needed for target[0:] = "abcd"

At position 0 (character 'a'):

• Start traversing Trie from root
• Find 'a' in Trie ✓
• Continue to position 1

At position 1 (character 'b'):

• 'b' exists as child of 'a' ✓
• We found valid prefix "ab" → Calculate: 1 + dfs(2)
• Continue to position 2

At position 2 (character 'c'):

• 'c' exists as child of 'b' ✓
• We found valid prefix "abc" → Calculate: 1 + dfs(3)
• Continue to position 3

At position 3 (character 'd'):

• 'd' doesn't exist as child of 'c' ✗
• Stop traversing from position 0

So from position 0, we have two choices:

• Use "ab" → 1 + dfs(2)
• Use "abc" → 1 + dfs(3)

Step 3: Solve dfs(2)

At position 2 (character 'c'):

• Start traversing Trie from root
• Find 'c' in Trie ✓
• Continue to position 3

At position 3 (character 'd'):

• 'd' exists as child of 'c' ✓
• We found valid prefix "cd" → Calculate: 1 + dfs(4)

dfs(4) returns 0 (base case - reached end of target)

Therefore, dfs(2) = 1 + 0 = 1

Step 4: Solve dfs(3)

At position 3 (character 'd'):

• Start traversing Trie from root
• Find 'd' in Trie ✓
• Continue to position 4 (out of bounds)
• We found valid prefix "d" → Calculate: 1 + dfs(4)

dfs(4) returns 0 (base case)

Therefore, dfs(3) = 1 + 0 = 1

Step 5: Calculate final result

Back to dfs(0):

• Using "ab": 1 + dfs(2) = 1 + 1 = 2
• Using "abc": 1 + dfs(3) = 1 + 1 = 2

Both paths give us 2, so dfs(0) = 2

Answer: 2

The target "abcd" can be formed using:

• "ab" + "cd" (2 valid strings)
• "abc" + "d" (2 valid strings)

The memoization ensures that dfs(3) and dfs(4) are only computed once, even though they might be reached through different paths. This optimization transforms what could be exponential time complexity into polynomial time.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2 + L)

The time complexity consists of two main parts:

• Trie Construction: Building the trie from all words takes O(L) time, where L is the total length of all words in the input array.
• DFS with Memoization: The dfs function can be called at most n times (once for each starting position in the target string). For each call to dfs(i), the inner loop iterates from position i to potentially position n-1, checking each character against the trie. This gives us O(n) work per call. With n possible calls and O(n) work each, the total time for DFS is O(n^2).

Therefore, the overall time complexity is O(n^2 + L).

Space Complexity: O(n + L)

The space complexity consists of:

• Trie Storage: The trie stores all the words, requiring O(L) space in the worst case, where L is the total length of all words.
• Memoization Cache: The @cache decorator stores results for at most n different values of i (from 0 to n-1), requiring O(n) space.
• Recursion Stack: In the worst case, the recursion depth can be O(n) when we match one character at a time.

Since the recursion stack and memoization cache both contribute O(n), and the trie contributes O(L), the total space complexity is O(n + L).

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

Common Pitfalls

1. Not Understanding Valid Strings are Prefixes, Not Just Substrings

A critical misunderstanding is thinking that any substring of words in the array can be used. The problem specifically requires prefixes - strings that start from the beginning of at least one word.

Incorrect Approach:

# Wrong: Checking if substring exists anywhere in words
def is_valid(substring):
    for word in words:
        if substring in word:  # This checks for any occurrence, not just prefix
            return True
    return False

Correct Approach:

# Right: Using Trie to check valid prefixes
# The Trie naturally enforces prefix matching from the start of words

2. Inefficient Prefix Checking Without Trie

Without a Trie, checking all possible prefixes becomes inefficient, leading to Time Limit Exceeded (TLE) for large inputs.

Inefficient Approach:

def minValidStrings(words, target):
    @cache
    def dfs(i):
        if i >= len(target):
            return 0
      
        result = float('inf')
        # Inefficient: For each position, checking all words and all lengths
        for j in range(i + 1, len(target) + 1):
            substring = target[i:j]
            for word in words:
                if word.startswith(substring) or substring == word[:len(substring)]:
                    result = min(result, 1 + dfs(j))
      
        return result

This approach has O(n² × m × k) complexity where n is target length, m is number of words, and k is average word length.

Efficient Solution: Using Trie reduces the complexity by allowing simultaneous prefix checking while traversing the target string character by character.

3. Memory Issues with String Slicing in Recursion

Creating substring copies in recursive calls can cause memory issues.

Memory-Intensive Approach:

def dfs(remaining_target):  # Passing substring instead of index
    if not remaining_target:
        return 0
  
    for i in range(1, len(remaining_target) + 1):
        prefix = remaining_target[:i]
        # Creates new string objects repeatedly
        result = min(result, 1 + dfs(remaining_target[i:]))

Memory-Efficient Solution: Pass indices instead of creating substring copies:

@cache
def dfs(start_index):  # Using index instead of substring
    if start_index >= len(target):
        return 0
    # Work with indices, not string copies

4. Forgetting to Handle the Impossible Case

Not properly returning -1 when it's impossible to form the target string.

Incomplete Handling:

def minValidStrings(words, target):
    result = dfs(0)
    return result  # Wrong: might return infinity

Proper Handling:

def minValidStrings(words, target):
    result = dfs(0)
    return result if result < float('inf') else -1

5. Not Using Memoization Leading to Exponential Time Complexity

Without memoization, the same subproblems are solved repeatedly.

Without Memoization:

def dfs(i):  # No @cache decorator
    if i >= n:
        return 0
    # This will recompute the same positions multiple times
    # Time complexity becomes exponential

With Memoization:

@cache  # Critical for performance
def dfs(i):
    if i >= n:
        return 0
    # Each position is computed only once

6. Incorrect Base Case in Recursion

Using wrong conditions for the base case can lead to incorrect results or infinite recursion.

Wrong Base Case:

def dfs(i):
    if i == len(target):  # Might miss the last character
        return 0
    # Or
    if i > len(target):  # Might cause index out of bounds
        return 0

Correct Base Case:

def dfs(i):
    if i >= len(target):  # Handles both exact match and beyond
        return 0