17

题目

方法一：暴力破解使用for循环一直遍历

var letterCombinations = function(digits) {
  if(digits.trim().length===0)return [];
  let arr = [
    [],[],['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']
  ]
  let ans = [];
  for(let i=0;i<digits.length;i++){
    if(i===0){
      for(let j=0;j<arr[digits[i]].length;j++){
        ans.push(arr[digits[i]][j]);
      }
    }else{
      let len = ans.length;
      for(let k=0;k<len;k++){
        let shift = ans.shift();
        for(let g=0;g<arr[digits[i]].length;g++){
          ans.push(shift+arr[digits[i]][g]);
        }
      }
    }
  }
  return ans;
};

方法二：回溯

var letterCombinations = function(digits) {
  if(digits.trim().length===0)return [];
  if(digits.trim().length===0)return [];
  let arr = [
    [],[],['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']
  ]
  let ans = [];
  function backtrack(idx,str){
    if(idx===digits.length){
      ans.push(str);
    }else{
      let temp = arr[digits[idx]];
      for(let i=0;i<temp.length;i++){
        backtrack(idx+1,`${str}${arr[digits[idx]][i]}`);
      }
    }
  }
  backtrack(0,'');
  return ans;
};