given an api which returns an array of words and an array of symbols display the word with their matched symbol surrounded by square brackets if the word string matches more than one symbol then choose the one with longest length ex microsoft matches i and cro example words array amazon microsoft google symbols i am cro na le abc output amazon microsoft google my solutionwrong i sorted the symbols array in descending order of length and ran loop over words array to find a symbol matchusing indexof in javascript which worked but i didn t make it through the interview i am guessing my solution was on2 and they expected an efficient algorithm output amazon microsoft google amazon microsoft google reversely sort the symbols according to their lengths once match append the wordreplaced to res process next word if this word matches no symbol append it another approach is to use a tree for the dictionary the symbols and then match brute force the complexity will depend on the dictionary if all are suffixes of the other it will be nm where m is the size of the dictionary for example in python reversely sort the symbols according to their lengths once match append the word_replaced to res process next word if this word matches no symbol append it another approach is to use a tree for the dictionary the symbols and then match brute force the complexity will depend on the dictionary if all are suffixes of the other it will be n m where m is the size of the dictionary for example in python
from functools import reduce


def match_symbol(words, symbols):
    import re
    combined = []
    for s in symbols:
        for c in words:
            r = re.search(s, c)
            if r:
                combined.append(re.sub(s, "[{}]".format(s), c))
    return combined

def match_symbol_1(words, symbols):
    res = []
    
    symbols = sorted(symbols, key=lambda _: len(_), reverse=True)
    for word in words:
        for symbol in symbols:
            word_replaced = ''
            
            if word.find(symbol) != -1:
                word_replaced = word.replace(symbol, '[' + symbol + ']')
                res.append(word_replaced)
                break
        
        if word_replaced == '':
            res.append(word)
    return res




class TreeNode:
    def __init__(self):
        self.c = dict()
        self.sym = None


def bracket(words, symbols):
    root = TreeNode()
    for s in symbols:
        t = root
        for char in s:
            if char not in t.c:
                t.c[char] = TreeNode()
            t = t.c[char]
        t.sym = s
    result = dict()
    for word in words:
        i = 0
        symlist = list()
        while i < len(word):
            j, t = i, root
            while j < len(word) and word[j] in t.c:
                t = t.c[word[j]]
                if t.sym is not None:
                    symlist.append((j + 1 - len(t.sym), j + 1, t.sym))
                j += 1
            i += 1
        if len(symlist) > 0:
            sym = reduce(lambda x, y: x if x[1] - x[0] >= y[1] - y[0] else y,
                         symlist)
            result[word] = "{}[{}]{}".format(word[:sym[0]], sym[2],
                                             word[sym[1]:])
    return tuple(word if word not in result else result[word] for word in words)