# 03. Possible Words From Phone Digits

The problem can be found at the following link: 🔗 [Question Link](https://www.geeksforgeeks.org/problems/possible-words-from-phone-digits-1587115620/1)

## **🧩 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

```cpp
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

```cpp
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++)**

```cpp
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;
    }
};
```

<details>

<summary>⚡ View Alternative Approaches with Code and Analysis</summary>

### 📊 **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.

```cpp
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.

```cpp
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.

```cpp
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**           | ★★★★★                     |

</details>

## **☕ Code (Java)**

```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)**

```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?](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let's make this learning journey more collaborative!

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

***

#### 📍Visitor Count

<div align="center"><img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" alt="Visitor counter"></div>
