Replace word with its shorter version

Question

I have a text and each word in this text can be replaced by word that I have in another list if it starts with the same letters and it's shorter that original. For example, my text is

'abdafb basrt casds dsasa a'

and list for replacement

['a', 'b']

. Thus, I will get

'a b casds dsasa a'

as a result.

slovar = list(map(str, input().split()))
text = list(map(str, input().split()))
for j in slovar:
    for i in range(len(text)):
        if text[i].startswith(j):
            text[i] = text[i][:len(j)]

print(' '. join(text))

my code has time limit error. How to make it faster?

SystemSigma_ · Answer

You can find a solution based on tries below.

Considering h = max(map(len, initials)),

worst case insert time is O(m*h), where m=len(initials),
worst case search time is capped at O(n*h) with n=len(words)

For a total max compute expense of O(n*m*h).

Since it is reasonable to assume n >> m >> h, we have O(n), linear with the number of words to replace.

class TrieNode:
      
    def __init__(self, max_children=26):
        self.children: list[None | TrieNode] = [None]*max_children
        self.is_end_of_initial = False
  
class Trie:
      
    def __init__(self):
        self.root = TrieNode()
  
    def _char_to_int(self,ch):
        return ord(ch)-ord('a')
  
    def insert(self, word: str):
        node = self.root

        for letter in word:
            index = self._char_to_int(letter)

            if not node.children[index]:
                node.children[index] = TrieNode()

            node = node.children[index]

        node.is_end_of_initial = True
  
    def get_replacement(self, word: str):
        node = self.root
        replacement = ''

        for letter in word:

            index = self._char_to_int(letter)

            if not node.children[index]:
                if node.is_end_of_initial:
                    return replacement
                else:
                    return word


            replacement += letter
            node = node.children[index]

        return replacement

t = Trie()

words = ['hello', 'world', 'hi', 'well', 'job', 'hellsbells', 'janitor', 'john']
initials = ['hel', 'w', 'jo']

for initial in initials:
    t.insert(initial)

replaced_words = [t.get_replacement(word) for word in words]
print(replaced_words)

Output

['hel', 'w', 'hi', 'w', 'jo', 'hel', 'janitor', 'jo']

Replace word with its shorter version

1 Answers