Three methods (Python)


  • 0
    M

    First solution (DFS with recursion, 79ms 3.19%):
    Care needs to be exercised with recursion because it may not differentiate if the initial string is empty or if you have arrived at a leaf. This is my very slow first solution.

    class Solution(object):
        d={"0":" ", "1":"*", "2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
        notfirst = None
        def letterCombinations(self, digits):
            if not len(digits):
                if self.notfirst:
                    return [""]
                else:
                    return []
            self.notfirst = True
            l=[]
            for i in self.d[digits[0]]:
                for j in self.letterCombinations(digits[1:]):
                    l.append(i+j)
            return l
    

    With simple optimization it gets a lot quicker (42ms, 72.65%):

    class Solution(object):
        d={"0":" ", "1":"*", "2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
        def letterCombinations(self, digits):
            """
            :type digits: str
            :rtype: List[str]
            """
            if not len(digits):
                return []
            l=[]
            for i in self.d[digits[0]]:
                for j in self.letterCombinations2(digits[1:]):
                    l.append(i+j)
            return l
        def letterCombinations2(self, digits):
            """
            :type digits: str
            :rtype: List[str]
            """
            if not len(digits):
                return [""]
            l=[]
            for i in self.d[digits[0]]:
                for j in self.letterCombinations2(digits[1:]):
                    l.append(i+j)
            return l
    

    Second solution (BFS with loop, 49ms, 40.93%):
    Apparently there are better algorithms with BFS, like appending to temp and replacing ans with temp, but this's what I wrote.

    class Solution(object):
        def letterCombinations(self, digits):
            """
            :type digits: str
            :rtype: List[str]
            """
            d={"0":" ", "1":"*", "2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
            if not digits:
                return []
            l=len(digits)
            ans = [[]]
            count = 0
            for index,i in enumerate(digits):
                while len(ans[count])==index:
                    for j in d[i]:
                        ans.append(ans[count]+[j])
                    count+=1
            return ["".join(i) for i in ans if len(i)==l]
    

    Final solution (maths???, 62ms, 14.71%):
    The intuitive version does not list in alphabetical order, but that can be tweaked and is probably not hard.

    class Solution(object):
        def letterCombinations(self, digits):
            """
            :type digits: str
            :rtype: List[str]
            """
            if not digits:
                return []
            d={"0":" ", "1":"*", "2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
            dx={"0":1, "1":1, "2":3, "3":3, "4":3, "5":3, "6":3, "7":4, "8":3, "9":4}
            d2=[1]
            for i in digits:
                d2.append(d2[-1]*dx[i])
            return ["".join([d[j][(i//d2[k])%dx[j]] for k,j in enumerate(digits)]) for i in xrange(d2[-1])]
    

Log in to reply
 

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