Share my AC python solution , 220ms ,


  • 0
    L

    First , I'm thinking of TRIE tree, however I think it's too complex for this problem, since I can easier use the string indexOf to check the same or not.

    1: build a same length words list.

    2: find the index which char is not "."

    3: find the same string, this is very fast, because I just use indexOf.

    class WordDictionary:
    
    def __init__(self):
    	self.root = {};
    
    # @param {string} word
    # @return {void}
    # Adds a word into the data structure.
    def addWord(self, word):
    	if(len(word) not in self.root):
    		self.root[len(word)]=[];
    	self.root[len(word)].append(word);
    
    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the data structure. A word could
    # contain the dot character '.' to represent any one letter.
    def search(self, word):
    	if(len(word) not in self.root):
    		return False;
    	sameLenWords=self.root[len(word)];
    
    	charIndexes=[];
    	for i in range(len(word)):
    		if(word[i]!='.'):
    			charIndexes.append(i);
    	
    	hasSame=False;
    	for sameLenWord in sameLenWords:
    		same=True;
    		for charIndex in charIndexes:
    			if(sameLenWord[charIndex] !=word[charIndex]):
    				same=False;
    				break;
    		if(same):
    			return True;
    	return hasSame;

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.