






















Given a list of unique strings words. I needed to remove every string that was a prefix of any other string in the list.
A string a was a prefix of string b if b starts with a and the length of a was strictly less than the length of b.
My output contained only the strings from words that were not a prefix of any other string in the list, and I kept their relative order the same as in the original input list.
Constraints:
1 ≤ words.length ≤ 10⁴
1 ≤ words[i].length ≤ 100
Each words[i] consists of lowercase English letters, spaces, or printable characters.
All strings in words are distinct.
Example 1:
Input: words = ["a", "abc", "abc hello", "bc"] Output: ["abc hello", "bc"] Explanation:
"a" is a prefix of both "abc" and "abc hello", so it is removed.
"abc" is a prefix of "abc hello", so it is removed.
"abc hello" and "bc" are not prefixes of any other string.
Example 2:
Input: words = ["a", "ab", "abc"] Output: ["abc"]
1 def remove_prefixes(words): 2 if not words: 3 return [] 4 5 # 1. Sort words lexicographically to bring prefixes next to their parents 6 # This takes O(N log N * L) where L is max string length 7 sorted_words = sorted(words) 8 prefixes_to_remove = set() 9 10 for i in range(len(sorted_words) - 1): 11 current_word = sorted_words[i] 12 next_word = sorted_words[i+1] 13 14 # 2. Check if the current word is a prefix of the next word 15 # .startswith() handles the prefix check efficiently 16 if next_word.startswith(current_word): 17 prefixes_to_remove.add(current_word) 18 19 # 3. Filter the original list to maintain relative order 20 return [w for w in words if w not in prefixes_to_remove] 21 22 # Example usage: 23 words1 = ["a", "abc", "abc hello", "bc"] 24 print(remove_prefixes(words1)) # Output: ["abc hello", "bc"] 25 26 words2 = ["a", "ab", "abc"] 27 print(remove_prefixes(words2)) # Output: ["abc"]
1 class TrieNode: 2 def __init__(self): 3 self.children = {} 4 self.is_end = False 5 6 class Trie: 7 def __init__(self): 8 self.root = TrieNode() 9 10 def insert(self, word): 11 node = self.root 12 for char in word: 13 if char not in node.children: 14 node.children[char] = TrieNode() 15 node = node.children[char] 16 node.is_end = True 17 18 def is_prefix_of_others(self, word): 19 node = self.root 20 for char in word: 21 node = node.children[char] 22 # If the node where the word ends has children, 23 # it means this word is a prefix of a longer string. 24 return len(node.children) > 0 25 26 def remove_prefixes_trie(words): 27 trie = Trie() 28 29 # 1. Build the Trie 30 for word in words: 31 trie.insert(word) 32 33 # 2. Filter words based on whether they have children in the Trie 34 # This maintains the original relative order 35 result = [] 36 for word in words: 37 if not trie.is_prefix_of_others(word): 38 result.append(word) 39 40 return result 41 42 # Test 43 words = ["a", "abc", "abc hello", "bc"] 44 print(remove_prefixes_trie(words)) # Output: ["abc hello", "bc"]
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。