电话号码的字母组合  


难度级别 中等
经常问 亚马逊 Apple Atlassian的 Capital One公司 Databricks 易趣 Facebook 谷歌 微软 摩根士丹利 神谕 Qualtrics Twilio 尤伯杯 VMware的 沃尔玛实验室
回溯 深度优先搜索 递归

在电话号码问题的字母组合中,我们给出了 绳子 包含从2到9的数字。问题在于,如果每个数字都分配有一些字母,则查找该数字可能代表的所有可能组合。 数字的分配在下面给出,就像电话按钮一样。

电话号码的字母组合

请注意,此处未将字母分配给1

使用案列  

"23"
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

分配给的字母 “2” ,那恭喜你, “ ABC” “3” ,那恭喜你, “ DEF” 因此字母的组合将为“ ad”,“ ae”,“ af”,“ bd”,“ be”,“ bf”,“ cd”,“ ce”和“ cf”

算法  

  1. 声明一个 队列 还有一个ArrayList和字符串 排列.
  2. 字符串数组应将值存储为给定的字符串keyWords [10] = {“,”,“ abc”,“ def”,“ ghi”,“ jkl”,“ mno”,“ pqrs”,“ tuv”,“ wxyz”};
  3. 首先,将一个空字符串推入队列
  4. 当队列中包含一些值时,它会在循环中进行迭代。
  5. 将队列前端的值存储到一个临时字符串
  6. 如果发现临时字符串的长度等于n(这是输入值的长度),则
  7. 将临时字符串的值添加到列表中。
  8. 否则,打开一个循环,在该循环中将字符串值初始化为副本= keys [number [temp.length()]];
  9. 将临时字符串添加到每个关键字的子字符串(0,1)并将其推入队列。
  10. 遍历它,直到队列中包含值。
  11. 退货清单。
参见
糖果Leetcode解决方案数量最多的孩子

说明  

假设给定输入为23,然后将其更改为整数。 并以与获取它相同的方式将其转换为数字数组。 然后,我们将输入值和该输入值的长度传递给我们命名为组合的函数。

在该函数中,我们还初始化了关键字字符串keyWords [10] = {“”,“”,“ abc”,“ def”,“ ghi”,“ jkl”,“ mno”,“ pqrs”,“ tuv”,“ wxyz”}

我们将这些值传递到另一个名为getCombination的函数中,在该函数中获取输出。

因此,我们以23为例,它分别存储在array = {2,3}中的0、1索引处。

因此,现在在函数中,我们声明了一个队列和一个列表,该列表将存储我们的输出。

我们将一个空字符串放入que中;
que =“”;

输入一个 while循环:我们将队列的前面放入temp并将其从que中删除,
温度=“”

现在,如果一个部分由于值与temp和n不同而无法执行。 因此,它执行其他部分将执行
复制= temp.length = 0 =>数字[0] = 2 =>键[2] =“ abc”
这意味着copy =“ abc”;

现在它会循环进行循环
并在a,b和c中添加que。

现在再次检查while(!que.isEmpty()),这是真的,因此它继续运行,并且在temp处于“ a”的队列前面,并删除了a。
复制= temp.length = 1 =>数字[1] = 3 =>键[3] =“ def”
因此,现在它将附加一个带有d,e和f的a并将其分别推入队列。

现在再次检查while(!que.isEmpty()),这是真的,因此它继续运行,并在temp的当前队列为b的情况下占据了前面,并删除了b。
复制= temp.length = 1 =>数字[1] = 3 =>键[3] =“ def”
因此,现在它将向b附加d,e和f并将其分别推入队列。

参见
具有k个不同数字的最小子数组

现在,它再次检查while(!que.isEmpty()),这是真的,因此它继续运行,并在temp中占据队列的前部,即“ c”并删除c。
复制= temp.length = 1 =>数字[1] = 3 =>键[3] =“ def”
因此,现在它将在c后面附加d,e和f并将其分别推入队列。

现在,如果它在temp中处于队列的前面,并发现temp.length等于n。 然后添加温度,然后依次添加我们得到的每个组合。
然后我们得到输出:(ad,ae,af,bd,be,bf,cd,ce,cf)

实施   

C ++程序查找电话号码的字母组合

#include<iostream>
#include<queue>
#include<sstream>
using namespace std;

vector<string> getCombination( int inputValue[], int n, string keyWords[])
{
    vector<string> list;

    queue<string> que;
    que.push("");

    while (!que.empty())
    {
        string temp = que.front();
        que.pop();
        if (temp.length() == n)
            list.push_back(temp);
        else
            for (auto getword : keyWords[inputValue[temp.length()]])
                que.push(temp + getword);
    }

    return list;
}

void combination( int inputValue[], int n)
{

    string keyWords[10]
        = { "", "", "abc", "def", "ghi", "jkl",
            "mno", "pqrs", "tuv", "wxyz"
          };

    vector<string> list= getCombination(inputValue, n, keyWords);

    for (auto word : list)
        cout << word << " ";

    return;
}

int main()
{
    string s="23";
    stringstream comb(s);
    int le=s.length();
    int inputValue[le];
    int i=0,x=0;
    comb>>x;
    while(x>0)
    {
        inputValue[le-i-1]=x%10;
        x/=10;
        i++;
    }
    int lengths = sizeof(inputValue) / sizeof(inputValue[0]);

    combination(inputValue, lengths);
    return 0;
}
ad ae af bd be bf cd ce cf

Java程序查找电话号码的字母组合

import java.util.*;

class combinationNumber {
  static ArrayList<String> getCombination(int[] number, int n, String[] keys) {
    ArrayList<String> getList = new ArrayList<>();

    Queue<String> que = new LinkedList<>();

    que.add("");

    while (!que.isEmpty()) {
      String temp = que.remove();

      if (temp.length() == n)
        getList.add(temp);
      else {
        String copy = keys[number[temp.length()]];
        for (int i = 0; i<copy.length(); i++) {
          que.add(temp + copy.charAt(i));
        }
      }
    }
    return getList;
  }

  static void combination(int[] inputValue, int n) {
    String[] keyWords = {
      "", "", "abc", "def", "ghi", "jkl",
      "mno", "pqrs", "tuv", "wxyz"
    };

    ArrayList<String> output = getCombination(inputValue, n, keyWords);

    for (int i = 0; i<output.size(); i++) {
      System.out.print(output.get(i) + " ");
    }
  }

  public static void main(String args[]) {
    String s = "23";
    int numb = Integer.valueOf(s);
    int i = 0;
    int[] inputValue = new int[s.length()];
    while (numb > 0) {
      inputValue[s.length() - i - 1] = numb % 10;
      numb /= 10;
      i++;
    }

    int lengths = inputValue.length;
    combination(inputValue, lengths);
  }
}
ad ae af bd be bf cd ce cf

复杂度分析  

时间复杂度

O(3N ×4M) 其中N是分配了3个字母(例如:2,3,4)的数字,M是分配了4个字母(例如:7,9)的数字。

参见
Excel工作表列号Leetcode解决方案

空间复杂度

O(3N ×4M) 其中N是分配了3个字母(例如:2,3,4)的数字,M是分配了4个字母(例如:7,9)的数字。