0017._letter_combinations_of_a_phone_number.md

Links:

1. https://leetcode.com/problems/letter-combinations-of-a-phone-number/
2. https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

Tags

1. 字符串
2. 回溯算法

Solution 1

itertools.product + 递归, dfs

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        import re
        from itertools import product # product(A, B) returns the same as ((x,y) for x in A for y in B).

        # 检查输入是否符合要求
        if not digits:
            return []

        if not re.search('^[2-9]+$', digits):
            return []

        digit_to_key = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz',
        }

        current_key = digit_to_key[digits[0]]

        if len(digits) == 1:
            '''
                because '' and [''] is difference.
                list(product('abc', '')) == [], 
                list(product('abc', ['']) != [].
            '''
            return list(current_key)    


        res_keys = self.letterCombinations(digits[1:])
        
        ans = [self._to_string(x) for x in product(current_key, res_keys)]

        return ans

    def _to_string(self, iterable):
        return ''.join(iterable)

Solution 2 :

用循环改写递归 使用标准库itertools.product + unpack(* operator)

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        import re
        from itertools import product # product(A, B) returns the same as ((x,y) for x in A for y in B).

        # 检查输入是否符合要求
        if not digits:
            return []

        if not re.search('^[2-9]+$', digits):
            return []

        digit_to_key = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz',
        }

        keys = []
        for digit in digits:
            keys.append(digit_to_key[digit])

        digits_product = product(*keys) 
        ans = list(map(self._to_string, digits_product))

        return ans
    
    def _to_string(self, iterable):
        return ''.join(iterable)

Solution3

用循环改写递归

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        import re
        from itertools import product # product(A, B) returns the same as ((x,y) for x in A for y in B).

        # 检查输入是否符合要求
        if not digits:
            return []

        if not re.search('^[2-9]+$', digits):
            return []

        digit_to_key = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz',
        }

        ans = ['']
        for digit in digits:
            current_key = digit_to_key[digit]
            # ans = list(map(self._to_string, product(ans, current_key)))
            ans = [self._to_string((x, y)) for x in ans for y in current_key]
            
        return ans

    def _to_string(self, iterable):
        return ''.join(iterable)

注意

Solution 2 和Solution3 的循环不同， Solution2是先求出所有的字符串，然后才去product. 而Solution3每次循环都做一次product

Solution 4

DFS

var (
	letterMap = []string{
		" ",    //0
		"",     //1
		"abc",  //2
		"def",  //3
		"ghi",  //4
		"jkl",  //5
		"mno",  //6
		"pqrs", //7
		"tuv",  //8
		"wxyz", //9
	}
	res   = []string{}
)

func letterCombinations(digits string) []string {
	if digits == "" {
		return []string{}
	}
	res = []string{}
	findCombination(&digits, 0, "")
	return res
}

func findCombination(digits *string, index int, s string) {
	if index == len(*digits) {
		res = append(res, s)
		return
	}
	num := (*digits)[index]
	letter := letterMap[num-'0']
	for i := 0; i < len(letter); i++ {
		findCombination(digits, index+1, s+string(letter[i]))
	}
	return
}

Solution 5

回溯

var phoneMap map[string]string = map[string]string{
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
}

var combinations []string

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    combinations = []string{}
    backtrack(digits, 0, "")
    return combinations
}

func backtrack(digits string, index int, combination string) {
    if index == len(digits) {
        combinations = append(combinations, combination)
        return
    } 

    digit := string(digits[index])
    letters := phoneMap[digit]
    lettersCount := len(letters)
    for i := 0; i < lettersCount; i++ {
        backtrack(digits, index + 1, combination + string(letters[i]))
    }
    
}