Блог

Проблема: Дан список business_names (строк) и поисковый запрос (строка). Возвращает список business_names, который содержит условие поиска в качестве префикса в business_names.

 Example 1.
Input:

business_names[] = { "burger king", "McDonald's", "super duper burger's", "subway", "pizza hut"}
searchTerm = "bur"

Ouput:
["burger king", "super duper burger's"]
 

Я попытался решить это следующим образом.

Но я хочу реализовать три подхода для решения этой проблемы. кто-нибудь, пожалуйста, помогите здесь? https://www.geeksforgeeks.org/trie-insert-and-search/

Любое линейное решение для решения

 def prefix(business_names, searchTerm):
    split = [i.split() for i in business_names]
    ans = []
    for name in split:
        for i in range(len(name)):
            query = ' '.join(name[i:])
            if query.startswith(searchTerm):
                ans.append(name)
                break
    return [' '.join(i) for i in ans]
 

Я не знаю, что это значит trie approach , и если это то, что вам нужно, но я бы написал проще — без join , range , len

Чтобы убедиться, что я также использую lower()

 business_names = ["burger king", "McDonald's", "super duper burger's", "subway", "pizza hut"]
searchTerm = "bur"


def prefix(business_names, searchTerm):
    searchTerm = searchTerm.lower()

    results  = []
    for name in business_names:
        for word in name.split(' '):
            word = word.lower()
            if word.startswith(searchTerm):
                results.append(name)
                break

    return results
    
print(prefix(business_names, searchTerm))
 

Редактировать:

Я взял код из ссылки и создал этот код.

Но мне пришлось изменить две вещи.

• он работает только с буквами a-z , поэтому я должен удалить ' и преобразовать в lower()
• он ищет только полные слова, но после удаления and pCrawl.isEndOfWord , return pCrawl != None and pCrawl.isEndOfWord кажется, он находит слова, которые соответствуют статистике searchTerm

Но у меня есть одно сомнение: может быть, тогда он сможет искать лучше O(n^2) , но сначала его нужно построить Trie , и ему также нужно некоторое время. Таким образом, это может быть полезно, когда вы всегда выполняете поиск в одном и том же тексте и вам приходится создавать Trie только один раз. Но вы должны создавать отдельные Trie файлы для каждого названия компании — и это не обязательно должно быть быстрее.

.

 class TrieNode: 
      
    # Trie node class 
    def __init__(self): 
        self.children = [None]*26
  
        # isEndOfWord is True if node represent the end of the word 
        self.isEndOfWord = False
  
class Trie: 
      
    # Trie data structure class 
    def __init__(self): 
        self.root = self.getNode() 
  
    def getNode(self): 
      
        # Returns new trie node (initialized to NULLs) 
        return TrieNode() 
  
    def _charToIndex(self,ch): 
          
        # private helper function 
        # Converts key current character into index 
        # use only 'a' through 'z' and lower case 
          
        return ord(ch)-ord('a') 
  
  
    def insert(self, key): 
          
        # If not present, inserts key into trie 
        # If the key is prefix of trie node,  
        # just marks leaf node 
        pCrawl = self.root 
        length = len(key) 
        for level in range(length): 
            index = self._charToIndex(key[level]) 
  
            # if current character is not present 
            if not pCrawl.children[index]: 
                pCrawl.children[index] = self.getNode() 
            pCrawl = pCrawl.children[index] 
  
        # mark last node as leaf 
        pCrawl.isEndOfWord = True
  
    def search(self, key): 
          
        # Search key in the trie 
        # Returns true if key presents  
        # in trie, else false 
        pCrawl = self.root 
        length = len(key) 
        for level in range(length): 
            index = self._charToIndex(key[level]) 
            if not pCrawl.children[index]: 
                return False
            pCrawl = pCrawl.children[index] 
  
        return pCrawl != None #and pCrawl.isEndOfWord  # <-- check `isEndOfWord` to search full words
  
# driver function 

def prefix(business_names, searchTerm):
  
    searchTerm = searchTerm.lower()

    results  = []
    
    for name in business_names:
    
        # Input keys (use only 'a' through 'z' and lower case) 
        # remove `'`  and convert to list with lower case words
        keys = name.lower().replace("'", "").split(" ")
        #print('keys:', keys)
        
        # Trie object 
        t = Trie() 
  
        # Construct trie 
        for key in keys: 
            #print('key:', key)
            t.insert(key) 

        # Search in trie
        if t.search(searchTerm) is True:
            results.append(name)        
        
    return results
  
if __name__ == '__main__': 

    business_names = ["burger king", "McDonald's", "super duper burger's", "subway", "pizza hut"]
    searchTerm = "bur"
    
    results = prefix(business_names, searchTerm)

    print( results )