Python Solution using Tries


  • 0
    S

    Create a trie out of the bank. Compare every character of the start word and end word. There are now two possibilities:

    1. If the characters do not match, then check if the end character is present in the current dictionary within the trie data structure. If it is not present, then return -1. Else, increment the counter and move to the dictionary within the current dict.
    2. If the characters match, then simply move into the dictionary within the current dict.

    Any suggestions for improvement will be greatly appreciated.

    _end = '_end'
    class Solution(object):
        def minMutation(self, start, end, bank):
            """
            :type start: str
            :type end: str
            :type bank: List[str]
            :rtype: int
            """
            if bank is None or len(bank) == 0:
                return -1
            
            self.createTrie(bank)
            
            curr_dict = self.root
            res = 0
            
            for i in range(8):
                if start[i] != end[i]:
                    if end[i] in curr_dict:
                        res += 1
                        curr_dict = curr_dict[end[i]]
                    else:
                        return -1
                else:
                    curr_dict = curr_dict[start[i]]
            
            return res
                
        def createTrie(self, bank):
            self.root = {}
            
            for word in bank:
                curr_dict = self.root
                
                for letter in word:
                    curr_dict = curr_dict.setdefault(letter, {})
                
                curr_dict[_end] = _end 
    

  • 1
    L

    Look good, but your solution doesn't handles when there is no direct path from start to end.

    try this case:
    "AAAA"
    "AAGT"
    [ "CAAA", "CCAA", "CCAT", "CCGT", "CAGT", "AAGT"]

    It will just assume that it can go from start to end by mutating 2 chars, but in reality you have to go trough 6 mutation.


  • 0

    @lasser Thanks I have added your test case. Note that the problem description mentions the string must have exactly 8 letters, so I have appended each of your string by 4 'A's.


  • 0
    M

    It makes sense to me but this solution doesn't seem to work for the following testcase:

    "AACCTTGG"
    "AATTCCGG"
    ["AATTCCGG","AACCTGGG","AACCCCGG","AACCTACC"]


Log in to reply
 

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