题目

给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，

如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。

请返回所有可行解 s 中最长长度。

示例 1：输入：arr = ["un","iq","ue"] 输出：4

解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。

示例 2：输入：arr = ["cha","r","act","ers"] 输出：6

解释：可能的解答有 "chaers" 和 "acters"。

示例 3：输入：arr = ["abcdefghijklmnopqrstuvwxyz"] 输出：26

提示：1 <= arr.length <= 16

1 <= arr[i].length <= 26

arr[i] 中只含有小写英文字母

解题思路分析

1、回溯-子集；时间复杂度O(n*2^n)，空间复杂度O(n*2^n)

var res []string

func maxLength(arr []string) int {
	res = make([]string, 0)
	dfs(arr, "", 0)
	maxValue := 0
	for i := 0; i < len(res); i++ {
		if check(res[i]) == true && len(res[i]) > maxValue {
			maxValue = len(res[i])
		}
	}
	return maxValue
}

func dfs(arr []string, path string, index int) {
	res = append(res, path)
	for i := index; i < len(arr); i++ {
		dfs(arr, path+arr[i], i+1)
	}
}

func check(s string) bool {
	arr := [26]int{}
	for i := 0; i < len(s); i++ {
		value := int(s[i] - 'a')
		arr[value]++
		if arr[value] > 1 {
			return false
		}
	}
	return true
}

2、回溯；时间复杂度O(n*2^n)，空间复杂度O(n)

var res int

func maxLength(arr []string) int {
	res = 0
	dfs(arr, "", 0)
	return res
}

func dfs(arr []string, path string, index int) {
	if check(path) == true && len(path) > res {
		res = len(path)
	}
	for i := index; i < len(arr); i++ {
		dfs(arr, path+arr[i], i+1)
	}
}

func check(s string) bool {
	arr := [26]int{}
	for i := 0; i < len(s); i++ {
		value := int(s[i] - 'a')
		arr[value]++
		if arr[value] > 1 {
			return false
		}
	}
	return true
}

3、回溯；时间复杂度O(n*2^n)，空间复杂度O(n)

var res int

func maxLength(arr []string) int {
	res = 0
	dfs(arr, "", 0)
	return res
}

func dfs(arr []string, path string, index int) {
	for i := index; i < len(arr); i++ {
		newStr := path + arr[i]
		if check(newStr) == true {
			if len(newStr) > res {
				res = len(newStr)
			}
			dfs(arr, path+arr[i], i+1)
		}
	}
}

func check(s string) bool {
	arr := [26]int{}
	for i := 0; i < len(s); i++ {
		value := int(s[i] - 'a')
		arr[value]++
		if arr[value] > 1 {
			return false
		}
	}
	return true
}

总结

Medium题目，考察回溯算法，本质上还是子集问题，参考leetcode 78.子集 的解法