題目敘述
題目會給定一個字串陣列arr最為輸入，我們可以任意選擇一組不包含重複字元的陣列子序列，將字串進行串接，成為字串s，請問字串s的最大長度是多少?
例如:
arr=["dog","cow","cat"]我們可以選擇"dog", "cat"進行串接，得到的字串s="dogcat"，s的最長長度為6
註:
"dog","cow"不能同時選進來，因為dog和cow有重複的字元o，這是題目的限制。
"cow","cat"也不能同時選進來，因為cow和cat有重複的字元c，這是題目的限制。
測試範例
Example 1:
Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All the valid concatenations are:
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
Maximum length is 4.
Example 2:
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").
Example 3:
Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26
Explanation: The only string in arr has all 26 characters.
約束條件
Constraints:
1 <= arr.length <= 16
輸入陣列arr的長度介於1 ~ 16 之間。
1 <= arr[i].length <= 26
每個字串的長度介於 1~26 之間。
arr[i]contains only lowercase English letters.
陣列元素皆為字串，裡面只會有小寫英文字母。
演算法
其實單獨對於每個字串arr[i]來說，只有兩種可能情況。
一種是被選進來，當作字串串接的對象。(前提是和已經選擇的字串彼此之間沒有重複的字元)
另一種是沒有被選進來，直接跳過。
我們可以用DFS+回溯法，遞迴展開每種可能的情況，並且在遞迴結束的地方更新字串串接的最大長度。
最後，回傳所有可能情況之下的串接字串最大長度，就是答案。
程式碼
class Solution:
def maxLength(self, arr: List[str]) -> int:
# Best length of character set, initialized as 0
self.max_length = 0
## parameter
# i: index of string array, arr
# cur_set: current character set so far
def dfs(i, cur_set):
## Base case aka stop condition
if i == len(arr):
# We've checking all possible combination
# Update max length of current character set
self.max_length = max(self.max_length, len(cur_set) )
return
## General case:
# Either we choose set_i, or skip set_i
set_i = set(arr[i])
# Option_#1: Select current set_i
if len( cur_set & set_i ) == 0 and ( len(set_i) == len(arr[i]) ):
dfs(i+1, cur_set | set_i )
# Option_#2: Skip current set_i
dfs(i+1, cur_set)
return
# ===========================================
dfs(i=0, cur_set=set() )
return self.max_length
複雜度分析
時間複雜度:
對於每條字串，遞迴展開所有可能情況，所需時間為O(2^n)。
每條字串有兩種可能: 1.選進來 或者 2.被略過。
空間複雜度:
遞迴深度最大為n，從第一條字串，遞迴展開到最後一條。所需stack深度為O(n)
關鍵知識點
當使用枚舉類的演算法去展開所有可能情況時，聯想到最常用的演算法框架:
DFS 深度優先搜索+ Backtracking 回溯法，必要的時候可以再額外使用pruning剪枝來排除不可能產生最優解的情況。
Reference:
[1] Maximum Length of a Concatenated String with Unique Characters -
