반응형
주어진 전화 번호가 나타낼 수있는 가능한 모든 문자 조합을 어떻게 인쇄 할 수 있습니까?
방금 첫 번째 프로그래밍 인터뷰를 시도했는데 질문 중 하나는 7 자리 전화 번호가 주어지고 각 숫자가 나타낼 수있는 모든 가능한 문자 조합을 인쇄 할 수있는 프로그램을 작성하는 것이 었습니다.
질문의 두 번째 부분은 이것이 12 자리 국제 번호라면 어떨까요? 디자인에 어떤 영향을 미칠까요?
인터뷰에서 작성한 코드는 없지만 그가 마음에 들지 않는 인상을 받았습니다.
이를 수행하는 가장 좋은 방법은 무엇입니까?
Python에서 반복 :
digit_map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
def word_numbers(input):
input = str(input)
ret = ['']
for char in input:
letters = digit_map.get(char, '')
ret = [prefix+letter for prefix in ret for letter in letters]
return ret
ret지금까지의 결과 목록입니다. 처음에는 하나의 항목 인 빈 문자열로 채워집니다. 그런 다음 입력 문자열의 각 문자에 대해 상단에 정의 된 사전에서 일치하는 문자 목록을 조회합니다. 그런 다음 목록 ret을 기존 접두사와 가능한 문자의 모든 조합으로 바꿉니다 .
전화 번호의 문자 조합 이라는 질문과 비슷합니다 . 여기 내 해결책이 있습니다.
결과가 메모리 제한을 초과하지 않는 한 임의의 자릿수에 대해 작동합니다.
import java.util.HashMap;
public class Solution {
public ArrayList<String> letterCombinations(String digits) {
ArrayList<String> res = new ArrayList<String>();
ArrayList<String> preres = new ArrayList<String>();
res.add("");
for(int i = 0; i < digits.length(); i++) {
String letters = map.get(digits.charAt(i));
if (letters.length() == 0)
continue;
for(String str : res) {
for(int j = 0; j < letters.length(); j++)
preres.add(str + letters.charAt(j));
}
res = preres;
preres = new ArrayList<String>();
}
return res;
}
static final HashMap<Character,String> map = new HashMap<Character,String>(){{
put('1', "");
put('2',"abc");
put('3',"def");
put('4',"ghi");
put('5',"jkl");
put('6',"mno");
put('7',"pqrs");
put('8',"tuv");
put('9',"wxyz");
put('0', "");
}} ;
}
12 자리 국제 번호가 디자인에 어떤 영향을 미치는지 잘 모르겠습니다.
편집 : 국제 번호도 처리됩니다.
재귀를 사용하는 Java에서 :
import java.util.LinkedList;
import java.util.List;
public class Main {
// Number-to-letter mappings in order from zero to nine
public static String mappings[][] = {
{"0"}, {"1"}, {"A", "B", "C"}, {"D", "E", "F"}, {"G", "H", "I"},
{"J", "K", "L"}, {"M", "N", "O"}, {"P", "Q", "R", "S"},
{"T", "U", "V"}, {"W", "X", "Y", "Z"}
};
public static void generateCombosHelper(List<String> combos,
String prefix, String remaining) {
// The current digit we are working with
int digit = Integer.parseInt(remaining.substring(0, 1));
if (remaining.length() == 1) {
// We have reached the last digit in the phone number, so add
// all possible prefix-digit combinations to the list
for (int i = 0; i < mappings[digit].length; i++) {
combos.add(prefix + mappings[digit][i]);
}
} else {
// Recursively call this method with each possible new
// prefix and the remaining part of the phone number.
for (int i = 0; i < mappings[digit].length; i++) {
generateCombosHelper(combos, prefix + mappings[digit][i],
remaining.substring(1));
}
}
}
public static List<String> generateCombos(String phoneNumber) {
// This will hold the final list of combinations
List<String> combos = new LinkedList<String>();
// Call the helper method with an empty prefix and the entire
// phone number as the remaining part.
generateCombosHelper(combos, "", phoneNumber);
return combos;
}
public static void main(String[] args) {
String phone = "3456789";
List<String> combos = generateCombos(phone);
for (String s : combos) {
System.out.println(s);
}
}
}
확실한 해결책은 숫자를 키 목록에 매핑하는 함수와 가능한 조합을 생성하는 함수입니다.
첫 번째는 분명하고 두 번째는 매우 큰 숫자가 될 수있는 약 3 ^ 개의 자릿수 조합이 있기 때문에 더 문제가됩니다.
이를 수행하는 한 가지 방법은 숫자의 숫자 (밑수 4)에서 숫자 일치에 대한 각 가능성을보고 카운터에 가까운 무언가를 구현하는 것입니다 (일반적으로 숫자에 매핑 할 수있는 문자가 4 개 미만이므로 일부 인스턴스를 뛰어 넘는 것입니다) ).
더 분명한 해결책은 중첩 루프 또는 재귀로, 둘 다 덜 우아하지만 제 생각에는 유효합니다.
주의해야 할 또 다른 사항은 많은 조합에 대해 이야기하고 있기 때문에 확장 성 문제 (예 : 가능성을 메모리에 유지하는 등)를 피하는 것입니다.
PS 질문의 또 다른 흥미로운 확장은 현지화입니다.
C ++ (재귀) :
string pattern[] = {"0",".,!","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};
ofstream keyout("keypad.txt");
void print_keypad(char* str, int k, vector<char> patt, int i){
if(str[k] != '\0')
{
int x = str[k] - '0';
for(int l = 0; l < pattern[x].length(); l++)
{
patt[i] = pattern[x][l];
print_keypad(str, k+1, patt, i+1);
}
keyout << endl;
}
else if(i == k)
{
string st(patt.data());
keyout << st << endl;
return;
}
}
이 함수는 'k'와 'i'가 0 인 상태에서 호출 할 수 있습니다.
논리를 이해하기 위해 더 많은 그림이 필요한 사람은 누구나 다음 출력과 재귀 기술을 결합 할 수 있습니다.
ADG
ADH
ADI
AEG
AEH
AEI
AFG
AFH
AFI
BDG
BDH
BDI
BEG
BEH
BEI
BFG
BFH
...
숫자 키보드에서 텍스트와 숫자는 같은 키에 배치됩니다. 예를 들어 2에는 "ABC"가 있습니다. 'A'로 시작하는 내용을 작성하려면 키 2를 한 번 입력해야합니다. 'B'를 입력하려면 키 2를 두 번 세 번 눌러 'C'를 입력합니다. 아래는 이러한 키패드의 사진입니다.
키패드 http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard.png
다이어그램에 표시된 키패드와 숫자 번호가 주어지면이 숫자를 눌러 가능한 모든 단어를 나열합니다.
예를 들어 입력 번호가 234 인 경우 구성 할 수있는 단어는 다음과 같습니다. (알파벳 순서)
먼저 몇 가지 계산을 해보겠습니다. 각 숫자가 n 개의 문자를 나타내는 7 자리 숫자로 몇 개의 단어가 가능합니까? 첫 번째 숫자의 경우 최대 4 개의 선택 항목이 있고 첫 번째 문자의 각 선택 항목에 대해 두 번째 숫자의 경우 최대 4 개의 선택 항목이 있습니다. 그래서 그것은 O (4 ^ n)이 될 간단한 수학입니다. 키 0과 1에는 해당하는 알파벳이없고 많은 문자에 3 개의 문자가 있으므로 4 ^ n은 최소 단어가 아닌 단어 수의 상한이됩니다.
이제 몇 가지 예를 들어 보겠습니다.
234 이상의 숫자. 패턴이 보이십니까? 예, 마지막 문자는 항상 G, H 또는 I이며 I에서 G로 값을 재설정 할 때마다 왼쪽에있는 숫자가 변경됩니다. 마찬가지로 두 번째 마지막 알파벳이 값을 재설정 할 때마다 마지막 세 번째 알파벳이 변경되는 식입니다. 첫 번째 문자는 모든 단어를 생성했을 때 한 번만 재설정됩니다. 이것은 다른 쪽에서도 볼 수 있습니다. 즉, i 위치의 문자가 변경 될 때마다 i + 1 위치의 문자는 가능한 모든 문자를 통과하여 끝에 도달 할 때까지 파급 효과를 만듭니다. 0과 1에는 연관된 문자가 없기 때문입니다. 이 숫자에 대한 반복이 없으므로 중단해야합니다.
재귀를 사용하여 구현하기 쉽기 때문에 두 번째 방법을 사용하겠습니다. 끝까지 가서 하나씩 돌아옵니다. 재귀를위한 완벽한 조건. 기본 케이스를 검색해 보겠습니다. 마지막 문자에 도달하면 마지막 숫자에 대해 가능한 모든 문자로 단어를 인쇄하고 반환합니다. Simple base case. 마지막 문자에 도달하면 마지막 숫자에 대해 가능한 모든 문자로 단어를 인쇄하고 반환합니다. 간단한 기본 케이스.
다음은 숫자 입력 번호에 해당하는 모든 가능한 단어를 인쇄하기위한 재귀 적 접근 방식의 C 구현입니다. 입력 번호는 코드를 단순화하기 위해 배열로 표시됩니다.
#include <stdio.h>
#include <string.h>
// hashTable[i] stores all characters that correspond to digit i in phone
const char hashTable[10][5] = {"", "", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"};
// A recursive function to print all possible words that can be obtained
// by input number[] of size n. The output words are one by one stored
// in output[]
void printWordsUtil(int number[], int curr_digit, char output[], int n)
{
// Base case, if current output word is prepared
int i;
if (curr_digit == n)
{
printf("%s ", output);
return ;
}
// Try all 3 possible characters for current digir in number[]
// and recur for remaining digits
for (i=0; i<strlen(hashTable[number[curr_digit]]); i++)
{
output[curr_digit] = hashTable[number[curr_digit]][i];
printWordsUtil(number, curr_digit+1, output, n);
if (number[curr_digit] == 0 || number[curr_digit] == 1)
return;
}
}
// A wrapper over printWordsUtil(). It creates an output array and
// calls printWordsUtil()
void printWords(int number[], int n)
{
char result[n+1];
result[n] ='\0';
printWordsUtil(number, 0, result, n);
}
//Driver program
int main(void)
{
int number[] = {2, 3, 4};
int n = sizeof(number)/sizeof(number[0]);
printWords(number, n);
return 0;
}
산출:
adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi
시간 복잡성 :
위 코드의 시간 복잡도는 O (4 ^ n)이며 여기서 n은 입력 된 숫자의 자릿수입니다.
참조 :
JavaScript에서. CustomCounter 클래스는 증가하는 인덱스를 처리합니다. 그런 다음 가능한 다른 조합을 출력하십시오.
var CustomCounter = function(min, max) {
this.min = min.slice(0)
this.max = max.slice(0)
this.curr = this.min.slice(0)
this.length = this.min.length
}
CustomCounter.prototype.increment = function() {
for (var i = this.length - 1, ii = 0; i >= ii; i--) {
this.curr[i] += 1
if (this.curr[i] > this.max[i]) {
this.curr[i] = 0
} else {
break
}
}
}
CustomCounter.prototype.is_max = function() {
for (var i = 0, ii = this.length; i < ii; ++i) {
if (this.curr[i] !== this.max[i]) {
return false
}
}
return true
}
var PhoneNumber = function(phone_number) {
this.phone_number = phone_number
this.combinations = []
}
PhoneNumber.number_to_combinations = {
1: ['1']
, 2: ['2', 'a', 'b', 'c']
, 3: ['3', 'd', 'e', 'f']
, 4: ['4', 'g', 'h', 'i']
, 5: ['5', 'j', 'k', 'l']
, 6: ['6', 'm', 'n', 'o']
, 7: ['7', 'p', 'q', 'r', 's']
, 8: ['8', 't', 'u', 'v']
, 9: ['9', 'w', 'x', 'y', 'z']
, 0: ['0', '+']
}
PhoneNumber.prototype.get_combination_by_digit = function(digit) {
return PhoneNumber.number_to_combinations[digit]
}
PhoneNumber.prototype.add_combination_by_indexes = function(indexes) {
var combination = ''
for (var i = 0, ii = indexes.length; i < ii; ++i) {
var phone_number_digit = this.phone_number[i]
combination += this.get_combination_by_digit(phone_number_digit)[indexes[i]]
}
this.combinations.push(combination)
}
PhoneNumber.prototype.update_combinations = function() {
var min_indexes = []
, max_indexes = []
for (var i = 0, ii = this.phone_number.length; i < ii; ++i) {
var digit = this.phone_number[i]
min_indexes.push(0)
max_indexes.push(this.get_combination_by_digit(digit).length - 1)
}
var c = new CustomCounter(min_indexes, max_indexes)
while(true) {
this.add_combination_by_indexes(c.curr)
c.increment()
if (c.is_max()) {
this.add_combination_by_indexes(c.curr)
break
}
}
}
var phone_number = new PhoneNumber('120')
phone_number.update_combinations()
console.log(phone_number.combinations)
이 문제는 이 leetcode 문제 와 유사합니다 . 이 문제에 대해 leetcode에 제출 한 답변은 다음과 같습니다 ( 설명은 github 및 비디오 확인 ).
따라서 가장 먼저 필요한 것은 숫자의 매핑을 유지하는 방법이며이를 위해지도를 사용할 수 있습니다.
private Map<Integer, String> getDigitMap() {
return Stream.of(
new AbstractMap.SimpleEntry<>(2, "abc"),
new AbstractMap.SimpleEntry<>(3, "def"),
new AbstractMap.SimpleEntry<>(4, "ghi"),
new AbstractMap.SimpleEntry<>(5, "jkl"),
new AbstractMap.SimpleEntry<>(6, "mno"),
new AbstractMap.SimpleEntry<>(7, "pqrs"),
new AbstractMap.SimpleEntry<>(8, "tuv"),
new AbstractMap.SimpleEntry<>(9, "wxyz"))
.collect(Collectors.toMap(AbstractMap.SimpleEntry::getKey,
AbstractMap.SimpleEntry::getValue));
}
위의 방법은지도를 준비하는 것이며 다음으로 사용할 방법은 제공된 숫자에 대한 매핑을 제공하는 것입니다.
private String getDigitMappings(String strDigit, Map<Integer,String> digitMap) {
int digit = Integer.valueOf(strDigit);
return digitMap.containsKey(digit) ? digitMap.get(digit) : "";
}
이 문제는 역 추적을 사용하여 해결할 수 있으며 역 추적 솔루션은 일반적으로 메서드 서명에 결과 컨테이너, 임시 결과, 인덱스가있는 원본 소스 등을 포함하는 구조를 갖습니다. 따라서 메서드 구조는 다음과 같은 형식이됩니다.
private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) {
// Condition to populate temp value to result
// explore other arrangements based on the next input digit
// Loop around the mappings of a digit and then to explore invoke the same method recursively
// Also need to remove the digit which was in temp at last so as to get proper value in temp for next cycle in loop
}
그리고 이제 메소드 본문을 다음과 같이 채울 수 있습니다 (결과는 목록에 보관되고, 문자열 작성기의 temp 등).
private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) {
if(start >= digits.length()) { // condition
result.add(temp.toString());
return;
}
String letters = getDigitMappings(digits.substring(start, start + 1), digitMap); // mappings of a digit to loop around
for (int i = 0; i < letters.length(); i++) {
temp.append(letters.charAt(i));
compute(result, temp, digits, start+1, digitMap); //explore for remaining digits
temp.deleteCharAt(temp.length() - 1); // remove last in temp
}
}
마지막으로 메서드는 다음과 같이 호출 할 수 있습니다.
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if(digits == null || digits.length() == 0) return result;
compute(result, new StringBuilder(), digits, 0, getDigitMap());
return result;
}
이제 숫자에 대한 최대 매핑 된 문자는 4가 될 수 있으며 (예 : 9에는 wxyz가 있음) 역 추적은 가능한 모든 배열 (상태 공간 트리)을 탐색하기위한 철저한 검색을 포함하므로 크기의 숫자에 n대해서는 4x4x4....n times복잡성이 될 것입니다 O(4^n).
namespace WordsFromPhoneNumber
{
/// <summary>
/// Summary description for WordsFromPhoneNumber
/// </summary>
[TestClass]
public class WordsFromPhoneNumber
{
private static string[] Chars = { "0", "1", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" };
public WordsFromPhoneNumber()
{
//
// TODO: Add constructor logic here
//
}
#region overhead
private TestContext testContextInstance;
/// <summary>
///Gets or sets the test context which provides
///information about and functionality for the current test run.
///</summary>
public TestContext TestContext
{
get
{
return testContextInstance;
}
set
{
testContextInstance = value;
}
}
#region Additional test attributes
//
// You can use the following additional attributes as you write your tests:
//
// Use ClassInitialize to run code before running the first test in the class
// [ClassInitialize()]
// public static void MyClassInitialize(TestContext testContext) { }
//
// Use ClassCleanup to run code after all tests in a class have run
// [ClassCleanup()]
// public static void MyClassCleanup() { }
//
// Use TestInitialize to run code before running each test
// [TestInitialize()]
// public void MyTestInitialize() { }
//
// Use TestCleanup to run code after each test has run
// [TestCleanup()]
// public void MyTestCleanup() { }
//
#endregion
[TestMethod]
public void TestMethod1()
{
IList<string> words = Words(new int[] { 2 });
Assert.IsNotNull(words, "null");
Assert.IsTrue(words.Count == 3, "count");
Assert.IsTrue(words[0] == "A", "a");
Assert.IsTrue(words[1] == "B", "b");
Assert.IsTrue(words[2] == "C", "c");
}
[TestMethod]
public void TestMethod23()
{
IList<string> words = Words(new int[] { 2 , 3});
Assert.IsNotNull(words, "null");
Assert.AreEqual(words.Count , 9, "count");
Assert.AreEqual(words[0] , "AD", "AD");
Assert.AreEqual(words[1] , "AE", "AE");
Assert.AreEqual(words[2] , "AF", "AF");
Assert.AreEqual(words[3] , "BD", "BD");
Assert.AreEqual(words[4] , "BE", "BE");
Assert.AreEqual(words[5] , "BF", "BF");
Assert.AreEqual(words[6] , "CD", "CD");
Assert.AreEqual(words[7] , "CE", "CE");
Assert.AreEqual(words[8] , "CF", "CF");
}
[TestMethod]
public void TestAll()
{
int[] number = new int [4];
Generate(number, 0);
}
private void Generate(int[] number, int index)
{
for (int x = 0; x <= 9; x += 3)
{
number[index] = x;
if (index == number.Length - 1)
{
var w = Words(number);
Assert.IsNotNull(w);
foreach (var xx in number)
{
Console.Write(xx.ToString());
}
Console.WriteLine(" possible words:\n");
foreach (var ww in w)
{
Console.Write("{0} ", ww);
}
Console.WriteLine("\n\n\n");
}
else
{
Generate(number, index + 1);
}
}
}
#endregion
private IList<string> Words(int[] number)
{
List<string> words = new List<string>(100);
Assert.IsNotNull(number, "null");
Assert.IsTrue(number.Length > 0, "length");
StringBuilder word = new StringBuilder(number.Length);
AddWords(number, 0, word, words);
return words;
}
private void AddWords(int[] number, int index, StringBuilder word, List<string> words)
{
Assert.IsTrue(index < number.Length, "index < length");
Assert.IsTrue(number[index] >= 0, "number >= 0");
Assert.IsTrue(number[index] <= 9, "number <= 9");
foreach (var c in Chars[number[index]].ToCharArray())
{
word.Append(c);
if (index < number.Length - 1)
{
AddWords(number, index + 1, word, words);
}
else
{
words.Add(word.ToString());
}
word.Length = word.Length - 1;
}
}
}
}
L [i] = 숫자 i가 나타낼 수있는 기호 인 목록 L을 사용합니다.
L [1] = @,.,! (예 : L [2] = a, b, c
기타.
그런 다음 다음과 같이 할 수 있습니다 (의사 C).
void f(int k, int st[])
{
if ( k > numberOfDigits )
{
print contents of st[];
return;
}
for each character c in L[Digit At Position k]
{
st[k] = c;
f(k + 1, st);
}
}
각 목록에 3 개의 문자가 포함되어 있다고 가정하면 7 자리 숫자는 3 ^ 7 개, 12 자리는 3 ^ 12 개로 많지 않습니다. 모든 조합이 필요하다면 더 나은 방법을 찾지 못했습니다. 재귀와 그 밖의 것을 피할 수 있지만 어떤 일이 있어도 이것보다 훨씬 빨리 무언가를 얻지는 못할 것입니다.
public class Permutation {
//display all combination attached to a 3 digit number
public static void main(String ar[]){
char data[][]= new char[][]{{'a','k','u'},
{'b','l','v'},
{'c','m','w'},
{'d','n','x'},
{'e','o','y'},
{'f','p','z'},
{'g','q','0'},
{'h','r','0'},
{'i','s','0'},
{'j','t','0'}};
int num1, num2, num3=0;
char tempdata[][]= new char[3][3];
StringBuilder number = new StringBuilder("324"); // a 3 digit number
//copy data to a tempdata array-------------------
num1= Integer.parseInt(number.substring(0,1));
tempdata[0] = data[num1];
num2= Integer.parseInt(number.substring(1,2));
tempdata[1] = data[num2];
num3= Integer.parseInt(number.substring(2,3));
tempdata[2] = data[num3];
//display all combinations--------------------
char temp2[][]=tempdata;
char tempd, tempd2;
int i,i2, i3=0;
for(i=0;i<3;i++){
tempd = temp2[0][i];
for (i2=0;i2<3;i2++){
tempd2 = temp2[1][i2];
for(i3=0;i3<3;i3++){
System.out.print(tempd);
System.out.print(tempd2);
System.out.print(temp2[2][i3]);
System.out.println();
}//for i3
}//for i2
}
}
}//end of class
#include <sstream>
#include <map>
#include <vector>
map< int, string> keyMap;
void MakeCombinations( string first, string joinThis , vector<string>& eachResult )
{
if( !first.size() )
return;
int length = joinThis.length();
vector<string> result;
while( length )
{
string each;
char firstCharacter = first.at(0);
each = firstCharacter;
each += joinThis[length -1];
length--;
result.push_back(each);
}
first = first.substr(1);
vector<string>::iterator begin = result.begin();
vector<string>::iterator end = result.end();
while( begin != end)
{
eachResult.push_back( *begin);
begin++;
}
return MakeCombinations( first, joinThis, eachResult);
}
void ProduceCombinations( int inNumber, vector<string>& result)
{
vector<string> inputUnits;
int number = inNumber;
while( number )
{
int lastdigit ;
lastdigit = number % 10;
number = number/10;
inputUnits.push_back( keyMap[lastdigit]);
}
if( inputUnits.size() == 2)
{
MakeCombinations(inputUnits[0], inputUnits[1], result);
}
else if ( inputUnits.size() > 2 )
{
MakeCombinations( inputUnits[0] , inputUnits[1], result);
vector<string>::iterator begin = inputUnits.begin();
vector<string>::iterator end = inputUnits.end();
begin += 2;
while( begin != end )
{
vector<string> intermediate = result;
vector<string>::iterator ibegin = intermediate.begin();
vector<string>::iterator iend = intermediate.end();
while( ibegin != iend)
{
MakeCombinations( *ibegin , *begin, result);
//resultbegin =
ibegin++;
}
begin++;
}
}
else
{
}
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
keyMap[1] = "";
keyMap[2] = "abc";
keyMap[3] = "def";
keyMap[4] = "ghi";
keyMap[5] = "jkl";
keyMap[6] = "mno";
keyMap[7] = "pqrs";
keyMap[8] = "tuv";
keyMap[9] = "wxyz";
keyMap[0] = "";
string inputStr;
getline(cin, inputStr);
int number = 0;
int length = inputStr.length();
int tens = 1;
while( length )
{
number += tens*(inputStr[length -1] - '0');
length--;
tens *= 10;
}
vector<string> r;
ProduceCombinations(number, r);
cout << "[" ;
vector<string>::iterator begin = r.begin();
vector<string>::iterator end = r.end();
while ( begin != end)
{
cout << *begin << "," ;
begin++;
}
cout << "]" ;
return 0;
}
Python 솔루션은 매우 경제적이며 생성기를 사용하기 때문에 메모리 사용 측면에서 효율적입니다.
import itertools
keys = dict(enumerate('::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ'.split(':')))
def words(number):
digits = map(int, str(number))
for ls in itertools.product(*map(keys.get, digits)):
yield ''.join(ls)
for w in words(258):
print w
분명히 itertools.product대부분의 문제를 해결하는 것입니다. 그러나 직접 쓰는 것은 어렵지 않습니다. 다음은 result모든 솔루션을 생성 하기 위해 배열 을 재사용하는 데주의를 기울이는 진행중인 솔루션과 f생성 된 단어를 캡처 하는 클로저 입니다. 결합하면 .NET 내부에서 O (log n) 메모리 사용이 제공됩니다 product.
package main
import (
"bytes"
"fmt"
"strconv"
)
func product(choices [][]byte, result []byte, i int, f func([]byte)) {
if i == len(result) {
f(result)
return
}
for _, c := range choices[i] {
result[i] = c
product(choices, result, i+1, f)
}
}
var keys = bytes.Split([]byte("::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ"), []byte(":"))
func words(num int, f func([]byte)) {
ch := [][]byte{}
for _, b := range strconv.Itoa(num) {
ch = append(ch, keys[b-'0'])
}
product(ch, make([]byte, len(ch)), 0, f)
}
func main() {
words(256, func(b []byte) { fmt.Println(string(b)) })
}
이것은의 C #을 포트입니다 이 대답.
암호
public class LetterCombinations
{
private static readonly Dictionary<string, string> Representations = new Dictionary<string, string>
{
{"2", "abc" },
{"3", "def" },
{"4", "ghi" },
{"5", "jkl" },
{"6", "mno" },
{"7", "pqrs" },
{"8", "tuv" },
{"9", "wxyz" },
};
public static List<string> FromPhoneNumber(string phoneNumber)
{
var result = new List<string> { string.Empty };
// go through each number in the phone
for (int i = 0; i < phoneNumber.Length; i++)
{
var pre = new List<string>();
foreach (var str in result)
{
var letters = Representations[phoneNumber[i].ToString()];
// go through each representation of the number
for (int j = 0; j < letters.Length; j++)
{
pre.Add(str + letters[j]);
}
}
result = pre;
}
return result;
}
}
단위 테스트
public class UnitTest
{
[TestMethod]
public void One_Digit_Yields_Three_Representations()
{
var sut = "2";
var expected = new List<string>{ "a", "b", "c" };
var actualResults = LetterCombinations.FromPhoneNumber(sut);
CollectionAssert.AreEqual(expected, actualResults);
}
[TestMethod]
public void Two_Digits_Yield_Nine_Representations()
{
var sut = "22";
var expected = new List<string> { "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc" };
var actualResults = LetterCombinations.FromPhoneNumber(sut);
CollectionAssert.AreEqual(expected, actualResults);
}
[TestMethod]
public void Three_Digits_Yield_ThirtyNine_Representations()
{
var sut = "222";
var actualResults = LetterCombinations.FromPhoneNumber(sut);
var possibleCombinations = Math.Pow(3,3); //27
Assert.AreEqual(possibleCombinations, actualResults.Count);
}
}
C #의이 버전은 상당히 효율적이며 비 서양 숫자 (예 : "۱۲۳۴۵۶۷")에서도 작동합니다.
static void Main(string[] args)
{
string phoneNumber = null;
if (1 <= args.Length)
phoneNumber = args[0];
if (string.IsNullOrEmpty(phoneNumber))
{
Console.WriteLine("No phone number supplied.");
return;
}
else
{
Console.WriteLine("Alphabetic phone numbers for \"{0}\":", phoneNumber);
foreach (string phoneNumberText in GetPhoneNumberCombos(phoneNumber))
Console.Write("{0}\t", phoneNumberText);
}
}
public static IEnumerable<string> GetPhoneNumberCombos(string phoneNumber)
{
phoneNumber = RemoveNondigits(phoneNumber);
if (string.IsNullOrEmpty(phoneNumber))
return new List<string>();
char[] combo = new char[phoneNumber.Length];
return GetRemainingPhoneNumberCombos(phoneNumber, combo, 0);
}
private static string RemoveNondigits(string phoneNumber)
{
if (phoneNumber == null)
return null;
StringBuilder sb = new StringBuilder();
foreach (char nextChar in phoneNumber)
if (char.IsDigit(nextChar))
sb.Append(nextChar);
return sb.ToString();
}
private static IEnumerable<string> GetRemainingPhoneNumberCombos(string phoneNumber, char[] combo, int nextDigitIndex)
{
if (combo.Length - 1 == nextDigitIndex)
{
foreach (char nextLetter in phoneNumberAlphaMapping[(int)char.GetNumericValue(phoneNumber[nextDigitIndex])])
{
combo[nextDigitIndex] = nextLetter;
yield return new string(combo);
}
}
else
{
foreach (char nextLetter in phoneNumberAlphaMapping[(int)char.GetNumericValue(phoneNumber[nextDigitIndex])])
{
combo[nextDigitIndex] = nextLetter;
foreach (string result in GetRemainingPhoneNumberCombos(phoneNumber, combo, nextDigitIndex + 1))
yield return result;
}
}
}
private static char[][] phoneNumberAlphaMapping = new char[][]
{
new char[] { '0' },
new char[] { '1' },
new char[] { 'a', 'b', 'c' },
new char[] { 'd', 'e', 'f' },
new char[] { 'g', 'h', 'i' },
new char[] { 'j', 'k', 'l' },
new char[] { 'm', 'n', 'o' },
new char[] { 'p', 'q', 'r', 's' },
new char[] { 't', 'u', 'v' },
new char[] { 'w', 'x', 'y', 'z' }
};
Oracle SQL : 모든 전화 번호 길이로 사용 가능하며 현지화를 쉽게 지원할 수 있습니다.
CREATE TABLE digit_character_map (digit number(1), character varchar2(1));
SELECT replace(permutations,' ','') AS permutations
FROM (SELECT sys_connect_by_path(map.CHARACTER,' ') AS permutations, LEVEL AS lvl
FROM digit_character_map map
START WITH map.digit = substr('12345',1,1)
CONNECT BY digit = substr('12345',LEVEL,1))
WHERE lvl = length('12345');
여기 통증 C에 대한 것이 있습니다. 이것은 효율적이지 않습니다 (사실 나는 그것이 전혀 없다고 생각합니다). 그러나 그것에 대한 몇 가지 흥미로운 측면이 있습니다.
- 숫자를 받아 문자열로 변환합니다.
- 다음 순차 문자열을 생성하기 위해 매번 시드 번호를 올립니다.
이것에 대해 좋은 점은 문자열의 크기에 실제 제한이 없다는 것입니다 (문자 제한 없음). 필요한 경우 대기만으로 더 길고 긴 문자열을 생성 할 수 있습니다.
#include <stdlib.h>
#include <stdio.h>
#define CHARACTER_RANGE 95 // The range of valid password characters
#define CHARACTER_OFFSET 32 // The offset of the first valid character
void main(int argc, char *argv[], char *env[])
{
int i;
long int string;
long int worker;
char *guess; // Current Generation
guess = (char*)malloc(1); // Allocate it so free doesn't fail
int cur;
for ( string = 0; ; string++ )
{
worker = string;
free(guess);
guess = (char*)malloc((string/CHARACTER_RANGE+1)*sizeof(char)); // Alocate for the number of characters we will need
for ( i = 0; worker > 0 && i < string/CHARACTER_RANGE + 1; i++ ) // Work out the string
{
cur = worker % CHARACTER_RANGE; // Take off the last digit
worker = (worker - cur) / CHARACTER_RANGE; // Advance the digits
cur += CHARACTER_OFFSET;
guess[i] = cur;
}
guess[i+1] = '\0'; // NULL terminate our string
printf("%s\t%d\n", guess, string);
}
}
static final String[] keypad = {"", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
String[] printAlphabet(int num){
if (num >= 0 && num < 10){
String[] retStr;
if (num == 0 || num ==1){
retStr = new String[]{""};
} else {
retStr = new String[keypad[num].length()];
for (int i = 0 ; i < keypad[num].length(); i++){
retStr[i] = String.valueOf(keypad[num].charAt(i));
}
}
return retStr;
}
String[] nxtStr = printAlphabet(num/10);
int digit = num % 10;
String[] curStr = null;
if(digit == 0 || digit == 1){
curStr = new String[]{""};
} else {
curStr = new String[keypad[digit].length()];
for (int i = 0; i < keypad[digit].length(); i++){
curStr[i] = String.valueOf(keypad[digit].charAt(i));
}
}
String[] result = new String[curStr.length * nxtStr.length];
int k=0;
for (String cStr : curStr){
for (String nStr : nxtStr){
result[k++] = nStr + cStr;
}
}
return result;
}
/**
* Simple Java implementation without any input/error checking
* (expects all digits as input)
**/
public class PhoneSpeller
{
private static final char[][] _letters = new char[][]{
{'0'},
{'1'},
{'A', 'B', 'C'},
{'D', 'E', 'F'},
{'G', 'H', 'I'},
{'J', 'K', 'L'},
{'M', 'N', 'O'},
{'P', 'Q', 'R', 'S'},
{'T', 'U', 'V'},
{'W', 'X', 'Y', 'Z'}
};
public static void main(String[] args)
{
if (args.length != 1)
{
System.out.println("Please run again with your phone number (no dashes)");
System.exit(0);
}
recursive_phoneSpell(args[0], 0, new ArrayList<String>());
}
private static void recursive_phoneSpell(String arg, int index, List<String> results)
{
if (index == arg.length())
{
printResults(results);
return;
}
int num = Integer.parseInt(arg.charAt(index)+"");
if (index==0)
{
for (int j = 0; j<_letters[num].length; j++)
{
results.add(_letters[num][j]+"");
}
recursive_phoneSpell(arg, index+1, results);
}
else
{
List<String> combos = new ArrayList<String>();
for (int j = 0; j<_letters[num].length; j++)
{
for (String result : results)
{
combos.add(result+_letters[num][j]);
}
}
recursive_phoneSpell(arg, index+1, combos);
}
}
private static void printResults(List<String> results)
{
for (String result : results)
{
System.out.println(result);
}
}
}
나는 오히려 초보자이기 때문에 내가 틀린 곳에서 나를 바로 잡으십시오.
먼저 공간과 시간의 복잡성을 조사합니다. factorial (7) = 5040의 경우 모든 재귀 알고리즘이 수행 할 수 있으므로 팩토리얼이기 때문에 정말 나쁩니다. 그러나 factorial (12) ~ = 4 * 10 ^ 8의 경우 재귀 솔루션에서 스택 오버플로가 발생할 수 있습니다.
그래서 나는 재귀 알고리즘을 시도하지 않을 것입니다. 루핑 솔루션은 "Next Permutation"을 사용하여 매우 간단합니다.
그래서 {0, 1, 2, 3, 4, 5}를 만들고 배열하고 모든 순열을 생성하고 인쇄하는 동안 각각의 문자로 교체합니다. 0 = A, 5 = F
다음 Perm 알고리즘은 다음과 같이 작동합니다. 예 : 주어진 1,3,5,4 다음 순열은 1,4,3,5입니다.
다음 파마를 찾는 단계.
오른쪽에서 왼쪽으로 감소하는 첫 번째 숫자를 찾습니다. 예 : 3
왼쪽에서 오른쪽으로, 예를 들어 3보다 큰 가장 낮은 숫자를 찾습니다. 4
이 숫자를 하위 집합을 반대로 바꿉니다. 1,4,5,3 역 하위 집합 1,4,3,5
다음 순열 (또는 회전)을 사용하여 특정 전화 번호에서 시작하는 1000 개의 순열을 표시하려는 경우 특정 순열 하위 집합을 생성합니다. 이렇게하면 메모리에 모든 숫자를 저장하지 않아도됩니다. 숫자를 4 바이트 정수로 저장하면 10 ^ 9 바이트 = 1GB!.
다음은 동일한 작업 코드입니다. 일련의 동일한 숫자가 발생할 때 각 조합의 가능성을 확인하는 각 단계의 재귀입니다 .... 복잡성 관점에서 이보다 더 나은 솔루션이 있는지 확실하지 않습니다. .....
문제가 있으면 알려주세요 ....
import java.util.ArrayList;
public class phonenumbers {
/**
* @param args
*/
public static String mappings[][] = {
{"0"}, {"1"}, {"A", "B", "C"}, {"D", "E", "F"}, {"G", "H", "I"},
{"J", "K", "L"}, {"M", "N", "O"}, {"P", "Q", "R", "S"},
{"T", "U", "V"}, {"W", "X", "Y", "Z"}
};
public static void main(String[] args) {
// TODO Auto-generated method stub
String phone = "3333456789";
ArrayList<String> list= generateAllnums(phone,"",0);
}
private static ArrayList<String> generateAllnums(String phone,String sofar,int j) {
// TODO Auto-generated method stub
//System.out.println(phone);
if(phone.isEmpty()){
System.out.println(sofar);
for(int k1=0;k1<sofar.length();k1++){
int m=sofar.toLowerCase().charAt(k1)-48;
if(m==-16)
continue;
int i=k1;
while(true && i<sofar.length()-2){
if(sofar.charAt(i+1)==' ')
break;
else if(sofar.charAt(i+1)==sofar.charAt(k1)){
i++;
}else{
break;
}
}
i=i-k1;
//System.out.print(" " + m +", " + i + " ");
System.out.print(mappings[m][i%3]);
k1=k1+i;
}
System.out.println();
return null;
}
int num= phone.charAt(j);
int k=0;
for(int i=j+1;i<phone.length();i++){
if(phone.charAt(i)==num){
k++;
}
}
if(k!=0){
int p=0;
ArrayList<String> list2= generateAllnums(phone.substring(p+1), sofar+phone.charAt(p)+ " ", 0);
ArrayList<String> list3= generateAllnums(phone.substring(p+1), sofar+phone.charAt(p), 0);
}
else{
ArrayList<String> list1= generateAllnums(phone.substring(1), sofar+phone.charAt(0), 0);
}
return null;
}
}
0과 1은 문자와 일치하지 않으므로 숫자에 자연스러운 중단 점을 만듭니다. 그러나 모든 숫자에서 발생하는 것은 아닙니다 (처음에는 0을 제외하고). 9 자리부터 시작하는 +49567892345와 같은 긴 숫자는 OutOfMemoryErrors로 이어질 수 있습니다. 따라서 숫자를 다음과 같은 그룹으로 나누는 것이 좋습니다.
- 01723 5864
- 0172 35864
짧은 부분에서 이해할 수 있는지 확인하십시오. 나는 그런 프로그램을 작성하고 친구들로부터 몇 가지 숫자를 테스트했지만, 한 단어의 긴 단어는 말할 것도없고 일치를 위해 사전에서 확인할 수있는 짧은 단어의 조합을 거의 발견하지 못했습니다.
그래서 내 결정은 가능한 조합을 표시하고 수를 손으로, 아마도 여러 번 나누도록 장려함으로써 완전 자동화가 아닌 검색 만 지원하는 것이 었 습니다.
그래서 + -RAD JUNG (+-bycicle boy)을 찾았습니다.
맞춤법 오류, 약어, 외국어, 단어로 된 숫자, 단어로 된 숫자 및 이름을 허용하는 경우 문제를 해결하지 않는 것보다 해결책을 찾을 수있는 기회가 훨씬 큽니다.
246848 => 2hot4u (too hot for you)
466368 => goodn8 (good night)
1325 => 1FCK (Football club)
53517 => JDK17 (Java Developer Kit)
인간이 관찰 할 수있는 것들입니다. 알고리즘이 그런 것들을 찾는 것은 다소 어렵습니다.
이것은 C ++ 11의 재귀 알고리즘입니다.
#include <iostream>
#include <array>
#include <list>
std::array<std::string, 10> pm = {
"0", "1", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"
};
void generate_mnemonic(const std::string& numbers, size_t i, std::string& m,
std::list<std::string>& mnemonics)
{
// Base case
if (numbers.size() == i) {
mnemonics.push_back(m);
return;
}
for (char c : pm[numbers[i] - '0']) {
m[i] = c;
generate_mnemonic(numbers, i + 1, m, mnemonics);
}
}
std::list<std::string> phone_number_mnemonics(const std::string& numbers)
{
std::list<std::string> mnemonics;
std::string m(numbers.size(), 0);
generate_mnemonic(numbers, 0, m, mnemonics);
return mnemonics;
}
int main() {
std::list<std::string> result = phone_number_mnemonics("2276696");
for (const std::string& s : result) {
std::cout << s << std::endl;
}
return 0;
}
나는 (이 최신 답변을 다시 썼다 위의 언급 ), C에서에 자바를 . 위의 코드에서는 555-5055와 같은 숫자가 전혀 작동하지 않기 때문에 0과 1 (0과 1)에 대한 지원도 포함했습니다.
여기있어. 일부 댓글은 보존됩니다.
public static void printPhoneWords(int[] number) {
char[] output = new char[number.length];
printWordsUtil(number,0,output);
}
static String[] phoneKeys= new String[]{"0", "1", "ABC", "DEF", "GHI", "JKL",
"MNO", "PQRS", "TUV", "WXYZ"};
private static void printWordsUtil(int[] number, int curDigIndex, char[] output) {
// Base case, if current output word is done
if (curDigIndex == output.length) {
System.out.print(String.valueOf(output) + " ");
return;
}
// Try all 3-4 possible characters for the current digit in number[]
// and recurse for the remaining digits
char curPhoneKey[] = phoneKeys[number[curDigIndex]].toCharArray();
for (int i = 0; i< curPhoneKey.length ; i++) {
output[curDigIndex] = curPhoneKey[i];
printWordsUtil(number, curDigIndex+1, output);
if (number[curDigIndex] <= 1) // for 0 or 1
return;
}
}
public static void main(String[] args) {
int number[] = {2, 3, 4};
printPhoneWords(number);
System.out.println();
}
private List<string> strs = new List<string>();
char[] numbersArray;
private int End = 0;
private int numberOfStrings;
private void PrintLetters(string numbers)
{
this.End = numbers.Length;
this.numbersArray = numbers.ToCharArray();
this.PrintAllCombinations(this.GetCharacters(this.numbersArray[0]), string.Empty, 0);
}
private void PrintAllCombinations(char[] letters, string output, int depth)
{
depth++;
for (int i = 0; i < letters.Length; i++)
{
if (depth != this.End)
{
output += letters[i];
this.PrintAllCombinations(this.GetCharacters(Convert.ToChar(this.numbersArray[depth])), output, depth);
output = output.Substring(0, output.Length - 1);
}
else
{
Console.WriteLine(output + letters[i] + (++numberOfStrings));
}
}
}
private char[] GetCharacters(char x)
{
char[] arr;
switch (x)
{
case '0': arr = new char[1] { '.' };
return arr;
case '1': arr = new char[1] { '.' };
return arr;
case '2': arr = new char[3] { 'a', 'b', 'c' };
return arr;
case '3': arr = new char[3] { 'd', 'e', 'f' };
return arr;
case '4': arr = new char[3] { 'g', 'h', 'i' };
return arr;
case '5': arr = new char[3] { 'j', 'k', 'l' };
return arr;
case '6': arr = new char[3] { 'm', 'n', 'o' };
return arr;
case '7': arr = new char[4] { 'p', 'q', 'r', 's' };
return arr;
case '8': arr = new char[3] { 't', 'u', 'v' };
return arr;
case '9': arr = new char[4] { 'w', 'x', 'y', 'z' };
return arr;
default: return null;
}
}
Objective-C의 한 가지 옵션 :
- (NSArray *)lettersForNumber:(NSNumber *)number {
switch ([number intValue]) {
case 2:
return @[@"A",@"B",@"C"];
case 3:
return @[@"D",@"E",@"F"];
case 4:
return @[@"G",@"H",@"I"];
case 5:
return @[@"J",@"K",@"L"];
case 6:
return @[@"M",@"N",@"O"];
case 7:
return @[@"P",@"Q",@"R",@"S"];
case 8:
return @[@"T",@"U",@"V"];
case 9:
return @[@"W",@"X",@"Y",@"Z"];
default:
return nil;
}
}
- (NSArray *)letterCombinationsForNumbers:(NSArray *)numbers {
NSMutableArray *combinations = [[NSMutableArray alloc] initWithObjects:@"", nil];
for (NSNumber *number in numbers) {
NSArray *lettersNumber = [self lettersForNumber:number];
//Ignore numbers that don't have associated letters
if (lettersNumber.count == 0) {
continue;
}
NSMutableArray *currentCombinations = [combinations mutableCopy];
combinations = [[NSMutableArray alloc] init];
for (NSString *letter in lettersNumber) {
for (NSString *letterInResult in currentCombinations) {
NSString *newString = [NSString stringWithFormat:@"%@%@", letterInResult, letter];
[combinations addObject:newString];
}
}
}
return combinations;
}
나는 루비에서 시도해 보았고 다른 방법을 생각해 냈습니다.이 시점에서 시간과 공간 O (?)처럼 효율적이지 않을 수 있지만 Ruby의 내장 Array.product 메서드를 사용하기 때문에 좋아합니다. 어떻게 생각해?
편집 : 위의 Python에서 매우 유사한 솔루션을 볼 수 있지만 대답을 추가했을 때 보지 못했습니다.
def phone_to_abc(phone)
phone_abc = [
'0', '1', 'abc', 'def', 'ghi',
'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'
]
phone_map = phone.chars.map { |x| phone_abc[x.to_i].chars }
result = phone_map[0]
for i in 1..phone_map.size-1
result = result.product(phone_map[i])
end
result.each { |x|
puts "#{x.join}"
}
end
phone_to_abc('86352')
중첩 루프를 사용하는 R 솔루션 :
# Create phone pad
two <- c("A", "B", "C")
three <- c("D", "E", "F")
four <- c("G", "H", "I")
five <- c("J", "K", "L")
six <- c("M", "N", "O", "P")
seven <- c("Q", "R", "S")
eight <- c("T", "U", "V")
nine <- c("W", "X", "Y", "Z")
# Choose three numbers
number_1 <- two
number_2 <- three
number_3 <- six
# create an object to save the combinations to
combinations <- NULL
# Loop through the letters in number_1
for(i in number_1){
# Loop through the letters in number_2
for(j in number_2){
# Loop through the letters in number_3
for(k in number_3){
# Add each of the letters to the combinations object
combinations <- c(combinations, paste0(i, j, k))
}
}
}
# Print all of the possible combinations
combinations
더 많은 루프와 샘플링 을 사용하는 또 다른 기괴한 R 솔루션을 블로그에 게시했습니다 .
이 접근 방식은 R을 사용하며 먼저 사전을 해당 숫자 표현으로 변환 한 다음이를 조회로 사용합니다.
변환은 내 컴퓨터에서 1 초 밖에 걸리지 않으며 (약 100,000 단어의 기본 Unix 사전에서 변환), 최대 100 개의 서로 다른 숫자 입력에 대한 일반적인 조회에는 총 0.1 초가 걸립니다.
library(data.table)
#example dictionary
dict.orig = tolower(readLines("/usr/share/dict/american-english"))
#split each word into its constituent letters
#words shorter than the longest padded with "" for simpler retrieval
dictDT = setDT(tstrsplit(dict.orig, split = "", fill = ""))
#lookup table for conversion
#NB: the following are found in the dictionary and would need
# to be handled separately -- ignoring here
# (accents should just be appended to
# matches for unaccented version):
# c("", "'", "á", "â", "å", "ä",
# "ç", "é", "è", "ê", "í", "ñ",
# "ó", "ô", "ö", "û", "ü")
lookup = data.table(num = c(rep('2', 3), rep('3', 3), rep('4', 3),
rep('5', 3), rep('6', 3), rep('7', 4),
rep('8', 3), rep('9', 4)),
let = letters)
#using the lookup table, convert to numeric
for (col in names(dictDT)) {
dictDT[lookup, (col) := i.num, on = setNames("let", col)]
}
#back to character vector
dict.num = do.call(paste0, dictDT)
#sort both for faster vector search
idx = order(dict.num)
dict.num = dict.num[idx]
dict.orig = dict.orig[idx]
possibilities = function(input) dict.orig[dict.num == input]
#sample output:
possibilities('269')
# [1] "amy" "bmw" "cox" "coy" "any" "bow" "box" "boy" "cow" "cox" "coy"
possibilities('22737')
# [1] "acres" "bards" "barer" "bares" "barfs" "baser" "bases" "caper"
# [9] "capes" "cards" "cares" "cases"
Scala 솔루션 :
def mnemonics(phoneNum: String, dict: IndexedSeq[String]): Iterable[String] = {
def mnemonics(d: Int, prefix: String): Seq[String] = {
if (d >= phoneNum.length) {
Seq(prefix)
} else {
for {
ch <- dict(phoneNum.charAt(d).asDigit)
num <- mnemonics(d + 1, s"$prefix$ch")
} yield num
}
}
mnemonics(0, "")
}
Assuming each digit maps to at most 4 characters, the number of recursive calls T satisfy the inequality T(n) <= 4T(n-1), which is of the order 4^n.
ReferenceURL : https://stackoverflow.com/questions/2344496/how-can-i-print-out-all-possible-letter-combinations-a-given-phone-number-can-re
반응형
'programing tip' 카테고리의 다른 글
| 클래스 이름의 대괄호는 무엇을 의미합니까? (0) | 2021.01.05 |
|---|---|
| maxRequestLength의 최대 값? (0) | 2021.01.05 |
| mysql 데이터베이스의 사용자 이름과 비밀번호를 찾는 방법 (0) | 2020.12.31 |
| 마이크로 벤치마킹이란 무엇입니까? (0) | 2020.12.31 |
| 커밋 할 때마다 git에 파일을 추가해야합니까? (0) | 2020.12.31 |