17. Letter Combinations of a Phone Number

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

題目敘述

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

解題想法

1.backtracking(通常用來解組合相關問題)

vector<string> res;

void backtracking(string digits, vector<string> map, string current, int index)
{
    if (index == digits.size()) //base case
    {
        if (current != "")
        {
            res.push_back(current);
            return;
        }
    }
    else
    {
        string s = map[digits[index] - '0']; //get index string in map
        for (int i = 0; i < s.size(); i++)
        {
            backtracking(digits, map, current + s[i], index + 1);
            //save s[i] in current and call the next
        }
    }
    return;
}

vector<string> letterCombinations(string digits)
{
    vector<string> map;
    map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    backtracking(digits, map, "", 0);
    return res;
}

時間複雜度為O(N^2)