題目

給定一個字串陣列 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 []stringfunc 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 intfunc 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 intfunc 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.子集 的解法