Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Letter Combinations of a Phone Number #15

Open
barretlee opened this issue Jul 19, 2017 · 4 comments
Open

Letter Combinations of a Phone Number #15

barretlee opened this issue Jul 19, 2017 · 4 comments

Comments

@barretlee
Copy link
Owner

本题难度:★★

给定一个纯数字的字符串,根据下面九宫格表返回所有可能的字母组合:

九宫格表

比如给定 "23",那么所有可能的输出为:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

注意:上面给出的是按照辞典顺序输出的,可以不考虑顺序。

@daghlny
Copy link

daghlny commented Jul 19, 2017

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

int dfs(string& s, int *numbers, int cur, int n)
{
    if ( n == 0 ) return 0;
    if ( cur == n ){
        cout << s << endl;
        return 0;
    }
    const string &cands = letters[numbers[cur]];
    for(int i = 0; i < cands.size(); ++i)
    {
        s.push_back(cands[i]);
        dfs(s, numbers, cur+1, n);
        s.erase(s.end()-1);
    }
    return 0;
}

int main(void)
{
    char numbers_str[100];
    scanf("%s", numbers_str);
    int *numbers = new int[strlen(numbers_str)];
    for(int i = 0; i < strlen(numbers_str); ++i)
        numbers[i] = static_cast<int>(numbers_str[i] - '0');
    string s;
    dfs( s, numbers, 0, strlen(numbers_str));
    delete[] numbers;
    return 0;
}

@dahuanggithub
Copy link

dahuanggithub commented Jul 20, 2017

function f(a){
  var lib = ['','',"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
  var res = [];
  var arr = [];
  for(var i=0;i<a.length;i++){
    if(lib[a[i]]!==''){
      arr.push(lib[a[i]]);
    }
  }
  if(arr.length<2){
    if(arr.length===0){return res;}
    res = arr[0].split("");
  }else{
    res = arr.reduce(function(x,y){
     var _arr = [];
     for(var i=0;i<x.length;i++){
      for(var j=0;j<y.length;j++){
        _arr.push(x[i]+y[j]);
      }
     }
    return _arr;
    });
  }
  return res;
}
console.log(f("102"));

@2609974827
Copy link

2609974827 commented Jul 28, 2017

var lujin = function(indexStr) {
	if (!(/^[0-9]+$/.test(indexStr))) {
		return '';
	}
	var dictionary = ['', "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
	var indexArr = indexStr.split('');
	var targetDictionary = [];
	for (var i = 0, l = indexArr.length; i < l; i++) {
		var tempArr = dictionary[indexArr[i]].split('');
		for (var j = 0, m = tempArr.length; j < m; j++) {
			tempArr[j] = {
				value: tempArr[j],
				x_axis: i,
				y_axis: j
			}
		}
		targetDictionary.push(tempArr);
	}
	var results = traversal(targetDictionary);
	console.log(targetDictionary);
	console.log(results);
};
var traversal = function(arr) {
	var results = [];
	var stockArr = new arrayStack();
	var lastTop = {}, //存储出栈元素
		temp = {}; //存储栈顶元素
	var i = 0; //避免死循环
	stockArr.push(arr[0][0]);
	while (stockArr.length() > 0) {
		i++;
		temp = stockArr.top();
		//如果到达终点记录本次路劲值
		if (temp.x_axis == arr.length - 1) {
			results.push(stockArr.toString());
		}
		//判断是否有下一层,并且下一层不是上次出栈元素
		if (arr[temp.x_axis + 1] && arr[temp.x_axis + 1][0] && lastTop.x_axis != temp.x_axis + 1) {
			stockArr.push(arr[temp.x_axis + 1][0]);
		} else {
			if (arr[temp.x_axis][temp.y_axis + 1]) {
				lastTop = stockArr.pop();
				stockArr.push(arr[temp.x_axis][temp.y_axis + 1]);
			} else {
				lastTop = stockArr.pop();
			}
		}
		//到达限制死循环点
		if (i == 1000) {
			console.log('到达限制死循环点');
			break;
		}
	}
	return results;
};
var arrayStack = function() {
	this.stock = [];
	this.push = function(ele) {
		this.stock.push(ele);
	};
	this.pop = function() {
		return this.stock.pop();
	};
	this.top = function() {
		return this.stock[this.stock.length - 1];
	};
	this.size = function() {
		return this.stock.length;
	};
	this.clear = function() {
		this.stock.splice(0);
		return true;
	};
	this.length = function() {
		return this.stock.length;
	};
	this.toString = function() {
		var tempStr = '';
		for (var i = 0, l = this.stock.length; i < l; i++) {
			tempStr += this.stock[i].value;
		}
		return tempStr;
	}
}

@barretlee
Copy link
Owner Author

这道题使用深度优先遍历会比较简单。停了一周多,本周继续~

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants