03. Possible Words From Phone Digits

✅ GFG solution to the Possible Words From Phone Digits problem: generate all possible letter combinations from phone keypad digits using iterative and backtracking approaches. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

You are given a keypad (as shown in the diagram) and an array arr[] containing digits. Your task is to list all possible words in any order which can be generated by pressing numbers in arr[] sequentially.

Note: Number 0 and 1 do not map to any letters. You can return the words in any order, the driver code will print them in sorted order.

📘 Examples

Example 1

Input: arr[] = [2, 3]
Output: [ad, ae, af, bd, be, bf, cd, ce, cf]
Explanation: When we press 2 and 3 total 3 x 3 = 9 possible words formed.

Example 2

Input: arr[] = [2]
Output: [a, b, c]
Explanation: When we press 2 total 3 possible words formed.

🔒 Constraints

• $1 \le \text{arr.size()} \le 9$

• $0 \le \text{arr}[i] \le 9$

✅ My Approach

The optimal approach uses an Iterative Build-Up technique to generate all possible letter combinations:

Iterative Cross-Product Generation

1. Initialize:

   • Create a keypad mapping array where index represents digit and value contains corresponding letters.

   • Start with a result vector containing an empty string [""].

2. Process Each Digit:

   • For each digit in the input array, skip if it's 0 or 1 (no letter mapping).

   • Create a temporary vector to store new combinations.

3. Generate Combinations:

   • For each existing string in the result vector, append each possible character from the current digit's letter mapping.

   • Use cross-product logic: if current result has m strings and digit has k letters, generate m × k new combinations.

4. Update Result:

   • Replace the result vector with the newly generated combinations using move semantics for efficiency.

5. Return Final Result:

   • After processing all digits, return the complete list of combinations.

📝 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(4^n × n), where n is the number of valid digits (2-9) in the array. In the worst case, each digit can map to 4 characters (like 7 and 9), and we generate 4^n combinations. Each combination takes O(n) time to build as we concatenate characters.

• Expected Auxiliary Space Complexity: O(4^n × n), as we store all possible combinations in the result vector. Each combination string has length up to n characters.

🧑‍💻 Code (C++)

class Solution {
public:
    vector<string> possibleWords(vector<int> &arr) {
        vector<string> res = {""};
        string keys[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        for (int d : arr) {
            if (d < 2 || d > 9) continue;
            vector<string> temp;
            for (string &s : res)
                for (char c : keys[d])
                    temp.push_back(s + c);
            res = move(temp);
        }
        return res;
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ Backtracking Approach

💡 Algorithm Steps:

1. Use recursive backtracking to build combinations one character at a time.

2. For each digit, iterate through its mapped characters.

3. Add character to current string and recurse to next digit.

4. Backtrack by removing the last character after exploring all paths.

class Solution {
    void solve(vector<int> &arr, int i, string cur, string keys[], vector<string> &ans) {
        if (i == arr.size()) { ans.push_back(cur); return; }
        if (arr[i] < 2 || arr[i] > 9) { solve(arr, i + 1, cur, keys, ans); return; }
        for (char c : keys[arr[i]]) solve(arr, i + 1, cur + c, keys, ans);
    }
public:
    vector<string> possibleWords(vector<int> &arr) {
        vector<string> ans;
        string keys[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        solve(arr, 0, "", keys, ans);
        return ans;
    }
};

📝 Complexity Analysis:

• Time: ⏱️ O(4^n) - Up to 4 characters per digit (worst case)

• Auxiliary Space: 💾 O(n) - Recursion stack depth

✅ Why This Approach?

• Classic recursive pattern for combinations

• Easy to understand and debug

• Natural fit for tree exploration problems

📊 3️⃣ Queue-Based BFS

💡 Algorithm Steps:

1. Use a queue to build combinations level by level (breadth-first).

2. Start with an empty string in the queue.

3. For each digit, process all current combinations and append each possible character.

4. Continue until all digits are processed.

class Solution {
public:
    vector<string> possibleWords(vector<int> &arr) {
        queue<string> q;
        q.push("");
        string keys[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        for (int d : arr) {
            if (d < 2 || d > 9) continue;
            int sz = q.size();
            while (sz--) {
                string cur = q.front(); q.pop();
                for (char c : keys[d]) q.push(cur + c);
            }
        }
        vector<string> res;
        while (!q.empty()) { res.push_back(q.front()); q.pop(); }
        return res;
    }
};

📝 Complexity Analysis:

• Time: ⏱️ O(4^n) - Generate all possible combinations

• Auxiliary Space: 💾 O(4^n) - Queue stores all intermediate combinations

✅ Why This Approach?

• Level-by-level construction for clear visualization

• Avoids recursion overhead

• Good for understanding combination generation process

📊 4️⃣ Dynamic Programming Build-Up

💡 Algorithm Steps:

1. Build combinations iteratively using dynamic programming concept.

2. Maintain current set of combinations and update for each digit.

3. For each new digit, cross-product current results with digit's characters.

4. Replace old results with newly formed combinations.

class Solution {
public:
    vector<string> possibleWords(vector<int> &arr) {
        string keys[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> dp = {""};
        for (int d : arr) {
            if (d < 2 || d > 9) continue;
            vector<string> next;
            next.reserve(dp.size() * keys[d].size());
            for (const string &s : dp)
                for (char c : keys[d])
                    next.push_back(s + c);
            dp = move(next);
        }
        return dp;
    }
};

📝 Complexity Analysis:

• Time: ⏱️ O(4^n) - Generate all combinations

• Auxiliary Space: 💾 O(4^n) - Store all combinations

✅ Why This Approach?

• Iterative solution avoiding recursion

• Memory pre-allocation with reserve() for efficiency

• Clean separation of digit processing logic

🆚 🔍 Comparison of Approaches

🚀 Approach	⏱️ Time Complexity	💾 Space Complexity	✅ Pros	⚠️ Cons
🏷️ Iterative Build	🟢 O(4^n)	🟢 O(4^n)	🚀 Fast with move semantics	💾 Creates temporary vectors
🔍 Backtracking	🟢 O(4^n)	🟢 O(n)	📖 Intuitive recursive pattern	🔄 Function call overhead
📊 Queue BFS	🟢 O(4^n)	🟡 O(4^n)	🎯 Level-by-level clarity	💾 Queue memory overhead
🔄 DP Build-Up	🟢 O(4^n)	🟢 O(4^n)	⭐ Memory pre-allocation	🔧 Similar to iterative

🏆 Best Choice Recommendation

🎯 Scenario	🎖️ Recommended Approach	🔥 Performance Rating
🏅 Optimal performance needed	🥇 Iterative Build	★★★★★
📖 Readability priority	🥈 Backtracking	★★★★★
🔧 Understanding combinations	🥉 Queue BFS	★★★★☆
🎯 Interview/Competitive	🏅 DP Build-Up	★★★★★

☕ Code (Java)

class Solution {
    public ArrayList<String> possibleWords(int[] arr) {
        ArrayList<String> res = new ArrayList<>();
        res.add("");
        String[] keys = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        for (int d : arr) {
            if (d < 2 || d > 9) continue;
            ArrayList<String> temp = new ArrayList<>();
            for (String s : res)
                for (char c : keys[d].toCharArray())
                    temp.add(s + c);
            res = temp;
        }
        return res;
    }
}

🐍 Code (Python)

class Solution:
    def possibleWords(self, arr):
        res = [""]
        keys = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        for d in arr:
            if d < 2 or d > 9: continue
            res = [s + c for s in res for c in keys[d]]
        return res

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count

Visitor counter