17.电话号码的字母组合

一、题目原型：

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

二、题目意思剖析：

其实呢就是一个排列组合，将字母按照有序的顺序组合起来。

/*
    2-abc
    3-def
    4-ghi
    5-jkl
    6-mno
    7-pqrs
    8-tuv
    9-wxyz
 
   输入："23"
   输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
   如果输入的是 245
   输出：["agj", "agk", "agl", "ahj", "ahk", "ahl", "aij", "aik", "ail"......
 */

三、解题思路：

我呢是用swift语法来做，但是逻辑思路都是相通的。
第一想到的应该是递归。通过递归，再加上一些判断条件，将对应的字符串加入进数组。

// 1.最外围的主方法
func letterCombinations(_ digits: String) -> [String] {
    if digits.isEmpty {
        return []
    }
    //  由于swift语法特性，需要将digits字符串包装为一个数组
    var strings: [String] = []
    for digit in digits {
        let str: String = String.init(digit)
        strings .append(str)
    }
    haha(strings,0)
    return result
}

// 2.核心代码实现
func haha(_ strings: [String], _ index: Int) {
    if str.count == strings.count {
        result .append(str)
        return
    }
    // 防止数组越界
    if index >= strings.count {
        return
    }
    // 1.首先我们需要一个电话号码base数组。
    let bases: [[String]] = [[""],[""],["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"]]
    // 2.通过index索引将strings对应的字符串元素转换为Int类型的索引
    // baseIndex : 电话号码(数字)索引,比如strings=["2","4","5"],baseIndex就是2,4,5
    let baseIndex: Int = (Int)(strings[index])!
    for i in 0..<bases[baseIndex].count {
        // 拿到子数组里对应的字母
        let baseStr: String = bases[baseIndex][i]
        // 1.如果当前正在添加第一个字母,就将str清空
        if index == 0 {
            str .removeAll()
        }
        /* 2.如果当前正在添加最后一个字母,并且不是第一个字母串,就删除str的最后一个字符
             比如index = 2,说明在添加第三个字母，如果i不等于0，就需要把最后一个字母删除。
             "agj", "agk", "agl"
             过程 : agj - ag - agk - ag - agl
         */
        else if index == strings.count - 1 && i != 0{
            str .removeLast()
        }
        else {
            // 3.如果str不为空，需要删除字母串的后面几位，通过index来设定
            // 用str的长度 - index得到后面需要删除的长度
            // "jmpt", "jmpu", "jmpv", "jmqt", "jmqu", "jmqv", "jmrt", "jmru", "jmrv", "jmst", "jmsu", "jmsv
            
            // 比如当前字符串为 jmrv，index为2，就需要删除后面 4 - 2 = 2，删除后面2位。
            // baseStr为s，然后接下来的baseStr为t。
            // 过程 : jmrv - jm - jms - jmst
            if !str.isEmpty {
                str .removeLast(str.count - index)
            }
        }
        str .append(baseStr)
        haha(strings, index + 1)
    }
}

四、小结

有时候这类题都是去找规律，我们需要把一些例子所得到的数据展示出来，然后去寻找规律，让计算的过程直观的表达出来。
注：可以在haha方法里加入一个indexs数组，result也不要限定条件来添加，然后直接在letterCombinations方法里打印出indexs和result的值。这样可以非常直观的查看添加过程。

func haha(_ strings: [String], _ index: Int) {
    indexs .append(index)
    result .append(str)
    、、、后面的代码不变
}

耗时12毫秒，超过100%的提交记录，总提交数25。

有任何疑问都可以留言，非常乐意一起探讨。😄