String Matching in an Array
Easy · Arrays & Hashing · Explanation and code example
Trie
How it works
We can use a suffix trie to solve this problem. For each word, we insert all its suffixes into the trie. Each node tracks how many times it has been visited. When searching for a word, if the terminal node has been visited more than once, the word appears as a substring in another word (since we inserted all suffixes, any substring of any word is a prefix of some suffix).
Steps
- Build a Trie with a count at each node.
- For each word, insert all its suffixes. For each character traversed, increment the count.
- For each word, search the trie by following the characters.
- If the count at the final node is greater than
1, the word is a substring of another word (or appears multiple times). Add it to the result. - Return the result list.
Complexity
- Time complexity:
O(n * m ^ 2) - Space complexity:
O(n * m ^ 2)extra space.O(n * m)space for the output list.
Where
nis the number of words, andmis the length of the longest word.
Things to watch for
Comparing a Word Against Itself
When checking if a word is a substring of another, you must skip the case where i == j (the same word). Without this check, every word would be found as a substring of itself and incorrectly added to the result.
Adding Duplicate Words to the Result
If a word appears as a substring in multiple other words, you should add it to the result only once. Using a break statement after finding the first match, or using a set to track added words, prevents duplicates in the output.
Python code example
from typing import List
class TrieNode:
def __init__(self):
self.children = [None] * 26
self.cnt = 0
class Trie:
def __init__(self):
self.root = TrieNode()
def insert_suffixes(self, word: str) -> None:
for i in range(len(word)):
node = self.root
for j in range(i, len(word)):
idx = ord(word[j]) - ord('a')
if not node.children[idx]:
node.children[idx] = TrieNode()
node = node.children[idx]
node.cnt += 1
def search(self, word: str) -> bool:
node = self.root
for c in word:
idx = ord(c) - ord('a')
node = node.children[idx]
return node.cnt > 1
class Solution:
def stringMatching(self, words: List[str]) -> List[str]:
res = []
trie = Trie()
for word in words:
trie.insert_suffixes(word)
for word in words:
if trie.search(word):
res.append(word)
return res
C++ code example
class TrieNode {
public:
TrieNode* children[26];
int cnt;
TrieNode() {
for (int i = 0; i < 26; i++) children[i] = nullptr;
cnt = 0;
}
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
void insertSuffixes(const string& word) {
for (int i = 0; i < word.size(); i++) {
TrieNode* node = root;
for (int j = i; j < word.size(); j++) {
int idx = word[j] - 'a';
if (!node->children[idx]) {
node->children[idx] = new TrieNode();
}
node = node->children[idx];
node->cnt++;
}
}
}
bool search(const string& word) {
TrieNode* node = root;
for (char c : word) {
int idx = c - 'a';
node = node->children[idx];
}
return node->cnt > 1;
}
};
class Solution {
public:
vector<string> stringMatching(vector<string>& words) {
vector<string> res;
Trie trie;
for (const string& word : words) {
trie.insertSuffixes(word);
}
for (const string& word : words) {
if (trie.search(word)) {
res.push_back(word);
}
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.