String Formation: Check if a Target String Can Be Formed from Concatenating Given Words

Question

## Problem

Given a list of words and a target string, determine if the target can be formed by concatenating one or more words from the list (each word can be used multiple times, order matters).

```python
from typing import List

def can_form(words: List[str], target: str) -> bool:
    pass
```

**Example:**
```
words  = ["ab", "cd", "abcd"]
target = "abcdab"

"abcd" + "ab" = "abcdab" -> True
Output: True

target = "abcab"
No valid concatenation -> False
Output: False
```

## Approach

DP where `dp[i]` is True if `target[:i]` can be formed. For each position `i`, check all words: if `dp[i - len(w)]` is True and `target[i-len(w):i] == w`, set `dp[i] = True`. Time: O(n * m) where n=len(target), m=total characters in words.

## Follow-ups

1. How do you count the total number of distinct ways to form the target?
2. How would you return one valid decomposition (list of words used)?
3. If the word list is very large, how does using a trie improve lookup performance?
4. What if words can only be used a limited number of times each?

String Formation: Check if a Target String Can Be Formed from Concatenating Given Words

Question Details

Full Details

Topics

More from Snowflake