Python 3 solution using Trie


#1

class TrieNode(object):

    def init(self):

        self.children = [None]* 26

        self.isEndOfWord = False

class Trie(object):

    def init(self):

        self.root = self._get_node()

    

    def _get_node(self):

        return TrieNode()

    

    def __char_to_index(self,ch):

        return ord(ch)-ord(‘a’)

    

    def insert(self, key):

        pointer = self.root

        for ch in key:

            index = self.__char_to_index(ch)

            if not pointer.children[index]:

                pointer.children[index] = self._get_node()

            pointer = pointer.children[index]

        

        pointer.isEndOfWord = True

    

    def search(self, key):

        pointer = self.root

        for ch in key:

            index = self.__char_to_index(ch)

            if not pointer.children[index]:

                return False

            else:

                pointer = pointer.children[index]

        

        if pointer != None and pointer.isEndOfWord == True:

            return True

        else:

            return False

class Solution:

    # @param A : string

    # @param B : list of strings

    # @return a list of integers

    def solve(self, A, B):

        good_words = A.split(’_’)

        t = Trie() 

        # Construct trie 

        for key in good_words: 

            t.insert(key)

        

        good_score = {}

        for i,x in enumerate(B):

            for word in x.split(’_’):

                good_score[i] = good_score.get(i,0) + (1 if t.search(word) else 0)

        return [x[0] for x in sorted(good_score.items(), key=lambda x: -x[1])]

A = “play_boy”

B = [ “smart_guy”, “girl_and_boy_play”, “play_ground” ]

s = Solution()

print(s.solve(A, B))