17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

关键字：所有组合
模式识别：搜索算法

解题思路：
自顶向下的递归实现深度搜索
定义子问题
在当前递归层结合子问题解决原问题

Swift

func letterCombinations(_ digits: String) -> [String] {guard !digits.isEmpty else { return [] }let phoneMap:[Character : String] = ["2": "abc", "3": "def", "4": "ghi", "5": "jkl","6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"]var combinations:[String] = [String]();var combination:String = ""//回朔法,func backTrack(_ index:Int) {if index == digits.count {combinations.append(combination)}else {let digit = digits[digits.index(digits.startIndex, offsetBy: index)]if let letters = phoneMap[digit] {for letter in letters {combination.append(letter)backTrack(index+1)combination.removeLast()}}}}backTrack(0)return combinations}

OC

//深度优先遍历
- (NSArray *)letterCombinations:(NSString *)digits {if (digits.length == 0) {return @[];}NSDictionary *phoneMap = @{@"2": @"abc", @"3": @"def", @"4": @"ghi", @"5": @"jkl",@"6": @"mno", @"7": @"pqrs", @"8": @"tuv", @"9": @"wxyz"};NSMutableArray *combinations = [NSMutableArray array];NSMutableString *combination = @"".mutableCopy;//回溯法[self backTrackWithCombinations:combinationscombination:combinationphoneMap:phoneMapdigits:digitsindex:0];return combinations.copy;
}- (void)backTrackWithCombinations:(NSMutableArray *)combinationscombination:(NSMutableString *)combinationphoneMap:(NSDictionary *)phoneMapdigits:(NSString *)digitsindex:(NSInteger)index {if (index == digits.length) {[combinations addObject:combination.copy];}else {NSString *digit = [digits substringWithRange:NSMakeRange(index, 1)];NSString *letters = phoneMap[digit];if (letters.length > 0) {for (NSInteger i=0; i<letters.length; i++) {unichar charac = [letters characterAtIndex:i];NSString *str = [NSString stringWithCharacters:&charac length:1];[combination appendString:str];[self backTrackWithCombinations:combinationscombination:combinationphoneMap:phoneMapdigits:digitsindex:index+1];[combination deleteCharactersInRange:NSMakeRange((combination).length-1, 1)];}}}
}