题目分析

这个题目的数据量是经典的BFS和DFS问题，这类问题难点较小，是笔试面试中常考的题型，也是小伙伴们必须要掌握的。为什么要介绍这个题目呢？是因为这个题目还使用到状态压缩和位运算的知识。

深度优先搜索

本题要注意两个小技巧

可能有一些字符串本身不满足条件，如”aa”，因此可以在arr中将其排除。
如果每一次搜索都需要判断26个字符是否重复出现，时间会变为原来的26倍，可以使用位运算，其中第n位为0说明没有出现过a+n字符，第n位为1说明出现过。如3，二进制为11，说明此时字符串为”ab”

关于深搜的思想已经介绍过很多次，这里不做过多介绍，思路非常简单，其中cur_val为当前的二进制数字，cur_bit为当前字符串个数，cur_loc为当前遍历到哪一个元素，遍历过的元素不需要重复遍历

算法的时间复杂度为$O(2^n)$，空间复杂度为$O(n)$

下面是Python语言的题解

class Solution:
    def maxLength(self, arr):
        def dfs(cur_val, cur_bit, cur_loc):
            nonlocal res
            res = max(res, cur_bit)
            for i in range(cur_loc, length):
                if not(cur_val & dic[arr[i]]):
                    dfs(cur_val | dic[arr[i]], cur_bit + len(arr[i]), i + 1)

        arr = list(filter(lambda x: len(set(x)) == len(x), arr))
        length = len(arr)
        res = 0
        dic = {x: sum([2 ** (ord(i) - ord('a')) for i in x]) for x in arr}
        dfs(0, 0, 0)
        return res

下面是Kotlin语言的题解

class Solution {
    fun maxLength(arr: List<String>): Int {
        val newArr = arr.filter { it.toSet().size == it.length }
        val dic = newArr.associate { it to it.sumBy { 1 shl (it - 'a') } }
        var res = 0
        val length = newArr.size
        fun dfs(curVal:Int, curBit:Int, curLoc:Int) {
            res = Math.max(res, curBit)
            for (i in curLoc until length) {
                val bit = dic[newArr[i]]!!
                if (curVal and bit == 0) {
                    dfs(curVal or bit, curBit + newArr[i].length, i + 1)
                }
            }
        }
        dfs(0,0,0)
        return res
    }
}

广度优先搜索

广搜和深搜的本质是一样的，但是需要使用额外的空间复杂度记录当前所有状态

算法的时间复杂度为$O(2^n)$，空间复杂度为$O(2^n)$

下面是Python语言的题解

class Solution:
    def maxLength(self, arr):
        arr = list(filter(lambda x: len(set(x)) == len(x), arr))
        queue = deque([[0, 0, 0]])
        length = len(arr)
        res = 0
        dic = {x: sum([2 ** (ord(i) - ord('a')) for i in x]) for x in arr}
        while queue:
            cur_val, cur_bit, cur_loc = queue.popleft()
            res = max(res, cur_bit)
            for i in range(cur_loc, length):
                if not(cur_val & dic[arr[i]]):
                    queue.append([cur_val | dic[arr[i]], cur_bit + len(arr[i]), i + 1])
        return res

下面是Kotlin语言的题解

class Solution {
    fun maxLength(arr: List<String>): Int {
        val newArr = arr.filter { it.toSet().size == it.length }
        val dic = newArr.associate { it to it.sumBy { 1 shl (it - 'a') } }
        var res = 0
        val length = newArr.size
        val queue = ArrayDeque<IntArray>()
        queue.add(intArrayOf(0, 0, 0))
        while (queue.isNotEmpty()) {
            val cur = queue.removeFirst()
            res = Math.max(res, cur[1])
            for (i in cur[2]..length - 1) {
                val bit = dic[newArr[i]]!!
                if (cur[0] and bit == 0) {
                    queue.add(intArrayOf(cur[0] or bit, cur[1] + newArr[i].length, i + 1))
                }
            }
        }
        return res
    }
}

对比Python和Kotlin两种语言，都可以在函数中嵌套定义函数，而且在Python中可以使用filter将元素进行过滤，还可以使用内置的表达式将列表元素按照要求转换为字典。在Kotlin中使用数组的成员方法filter将元素进行过滤，使用associate方法将数组转换为字典，非常方便，极大减少代码量。

刷题总结

这类题目是必须掌握的，小伙伴们可以进行总结分类，多做一些BFS和DFS的题目，就会发现这类题目都有一个固定的模板，BFS是创建queue，DFS是进行回溯。