Leetcode 17 Solution

This article provides solution to leetcode question 17 (letter-combinations-of-a-phone-number)
Categories:
Tags:
Access this page by simply typing in "lcs 17" in your browser address bar if you have bunnylol configured.

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

Thinking Process

Finding all the combinations means we’ll have to iterate all the cases without missing a single one. We typically do that with a DFS recursion.

Whenever we try to design a DFS algorithm, always do the following two things:

  • define the states
  • define the state transition tree

The state of the algorithm can be represented by (i, curr), where i is current index of digit, and curr means the current string formed.

  • Apparently, if i == len(digit), we reached to an end, we can append curr to the final result.
  • Otherwise, find out the matching characters, and for each of them, append it to curr str, and iterate for the index i + 1.

Time & Space Complexity

Assuming N is the length of digit

  • Time complexity: O(2^N)
  • Space complexity: O(N)

Solution

class Solution {
    vector<string> m_res;
    vector<string> m_chars;

public:
    void letterCombinations(const string& digits, int i, string& curr) {
        if (i == digits.size())
        {
            if (curr.size() != 0)
                m_res.push_back(curr);
            return;
        }

        int digit = digits[i] - '0';

        for (const char& ch : m_chars[digit])
        {
            curr += ch;
            letterCombinations(digits, i + 1, curr);
            curr = curr.substr(0, curr.size() - 1);
        }
    }

    vector<string> letterCombinations(string digits) {
        m_chars.push_back("");
        m_chars.push_back("");
        m_chars.push_back("abc");
        m_chars.push_back("def");
        m_chars.push_back("ghi");
        m_chars.push_back("jkl");
        m_chars.push_back("mno");
        m_chars.push_back("pqrs");
        m_chars.push_back("tuv");
        m_chars.push_back("wxyz");

        string curr;

        letterCombinations(digits, 0, curr);
        return m_res;
    }
};