一魚多吃 用DFS來解英文字母覆蓋問題_Leetcode #1239

Susan Holt Simpson on Unsplash

題目敘述

題目會給定一個字串陣列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 -