most_freq_word.py

# https://practice.geeksforgeeks.org/problems/most-frequent-word-in-an-array-of-strings/0
class TrieNode:
    def __init__(self):
        self.children = [None] * 52
        self.is_end_of_word = False

    def find_if_leaf_node(self):
        return self.is_end_of_word

    def find_if_free_node(self):
        for child in self.children:
            if child:
                return False
        return True


class Trie:
    def __init__(self):
        self.root = self.get_node()
        # number of keys stored in the trie
        self.count = 0

    def get_node(self):
        return TrieNode()

    def _char_to_index(self, ch):
        idx = ord(ch) - ord('A') 
        if idx > 25:
            idx = ord(ch) - ord('a') + 26
        return idx
        
    def _index_to_char(self, idx):
        if idx < 26:
            return chr(idx + ord('A')) 
        else:
            return chr(idx + ord('a') - 26) 

    def insert(self, key):
        p_crawl = self.root

        for a_char in key:
            idx = self._char_to_index(a_char)
            if not p_crawl.children[idx]:
                p_crawl.children[idx] = self.get_node()
            p_crawl = p_crawl.children[idx]
        if not p_crawl.find_if_leaf_node():
            p_crawl.is_end_of_word = 1
        else:
            p_crawl.is_end_of_word += 1
        pass
        # print('key to insert is ', key)

    def search(self, key):
        p_crawl = self.root

        for a_char in key:
            idx = self._char_to_index(a_char)
            if not p_crawl.children[idx]:
                return False
            p_crawl = p_crawl.children[idx]
        return p_crawl and p_crawl.is_end_of_word

    # different possibilities
    # part of ip_str is sub_string of string in trie
    # whole ip_str is sub_string of string in trie but is not part of trie
    # whole ip_str is sub_string of string in trie and also is part of trie
    # whole ip_str is part of trie and is only one string in that branch
    # whole ip_str is part of trie and also holds other sub_strings which are part of trie
    def _delete_helper(self, p_node, key, level):
        # needs to be checked as the input string may not be
        # contained in trie and also not a sub string of
        # strings exits in trie
        if p_node:
            # this condition is because the input string may be part of
            # a sting in trie but might not be stored in trie
            if level == len(key):
                # this condition is not necessary as it does not add any
                # change even if it is removed
                if p_node.find_if_leaf_node():
                    p_node.is_end_of_word = False
                # last node will be deleted only when
                # last char of input is last node of a branch
                return p_node.find_if_free_node()
            else:
                index = self._char_to_index(key[level])
                if self._delete_helper(p_node.children[index],
                                       key, level + 1):
                    p_node.children[index] = None
                    return (not p_node.find_if_leaf_node() and
                            p_node.find_if_free_node())
        return False

    def delete_key(self, key):
        # input may be the only string for that branch
        # it may be part of another string
        # it may hold another string in it
        # the input may be substring of a string in trie but is not stored itself
        key_length = len(key)
        if key_length > 0:
            self._delete_helper(self.root, key, 0)


    def pre_order_util(self, c_node, c_str, max_vals):
        if c_node.find_if_leaf_node():
            # print('c_str', c_str)
            # print('true here')
            # print('leaf node is {}'.format(c_str))
            if max_vals[0] < c_node.find_if_leaf_node():
                max_vals[0] = c_node.find_if_leaf_node()
                # print('c_str maxted', c_str)
                max_vals[1] = c_str

        for idx in range(len(c_node.children)):
            if c_node.children[idx]:
                self.pre_order_util(c_node.children[idx], c_str + self._index_to_char(idx),
                                    max_vals)
            
    def pre_order(self):
        c_node = self.root
        max_vals = [0, '']
        self.pre_order_util(c_node, '', max_vals)
        print(max_vals[1])


test_cases = int(input().strip())

for a_tc in range(test_cases):
    str_cnt = (input())
    str_list = input().strip().split()
    # print(str_list)
    a_trie = Trie()

    for a_str in str_list:
        # print(a_str)
        # print(wc, end=' ')
        a_trie.insert(a_str)
    a_trie.pre_order()