LeetCodeProblems/letterCombination.cpp at main · iambharatks/LeetCodeProblems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>

using namespace std;

//   Letter Combinations of a Phone Number

class Solution
{
public:
    void preCompute(vector<vector<char>> &a)
    {
        char c = 'a';
        int j = 0, u;
        for (int i = 2; i < 10; i++)
        {
            j = 0;
            if (i == 7 || i == 9)
                u = 4;
            else
                u = 3;
            while (j < u)
            {
                a[i].push_back(c++);
                j++;
            }
        }
    }
    void dfs(string digits, int idx, vector<string> &ans, vector<vector<char>> a, string s = "")
    {
        if (idx >= digits.size())
        {
            ans.push_back(s);
            return;
        }
        for (char c : a[digits[idx] - '0'])
            dfs(digits, idx + 1, ans, a, s + c);
    }
    vector<string> letterCombinations(string digits)
    {
        if (digits.size() == 0)
            return {};
        vector<vector<char>> a(10);
        vector<string> ans;
        preCompute(a);
        // for (int i = 2; i <= 9; ++i)
        // {
        //     cout << i << "->";
        //     for (char c : a[i])
        //         cout << c << " ";
        //     cout << '\n';
        // }
        dfs(digits, 0, ans, a);
        return ans;
    }
};

class Optimized
{
    const vector<string> a = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public:
    vector<string> letterCombinations(string digits)
    {
        if (digits.size() == 0)
            return {};
        vector<string> ans, tmp;
        ans.push_back("");
        for (char digit : digits)
        {
            for (char c : a[digit - '0'])
            {
                for (string s : ans)
                    tmp.push_back(s + c);
            }
            swap(ans, tmp);
            tmp.clear();
        }
        return ans;
    }
};

int main()
{
    string digits;
    cin >> digits;

    vector<string> ans = Optimized().letterCombinations(digits);
    for (string s : ans)
        cout << s << " ";
}