o078. 3. 缺字問題

 題目敘述：

給定一個大小為 K 個字母的集合和字串 S，求出在使用該集合所組出長度為 L 字串中，不為字串 S 子字串的最小字典序字串為何。

自如字母集合{a,c,m}，其能組出長度為 2 的字串字典序由小到大排序為： aa < ac < am  < ca < cc < cm < ma < mc < mm。字串 S 為accaamcm，因此 ma 為不在 S 內的最小字典序字串。

這題看起來就很dfs，一般APCS第三題時間上是不會過關，但這題可以，想必官方考慮到國高中生期末考將至，難度有稍微調降了。簡單來說，想辦法求出a,c,m中不重複的所有排序組合。

以下是超白話思考順序

DFS思考的重點有兩個，每次要做什麼，終止條件是什麼。

啥都還沒想到的時候就先寫出

def dfs():#先把函式建起來

再來開始思考每次呼叫函示要做什麼，以這題為例，我們要嘗試在函式內組出不同的字母排列組合，所以應該需要一個字串參數帶入函式之中。所以：

def dfs(s):

有了參數後，可以想想看終止條件是什麼，終止條件就是組出長度為L的字串，所以：

def dfs(s):

    if len(s) == L:

        dosomething

長度到了之後呢，我們程式的目標是要找出不在字串S中的子字串啊，所以：

def dfs(s):

    if len(s) == L:

        if s not in S:#代表s不在S之中

            print(s)

            return False#不要繼續找了

        return True#繼續找吧

    for i in k:

        if dfs(ss+i) == False:

            return False

k = list(input())

l = int(input())

S = input()

dfs("" )

再加上剪枝(優化加速)，就變成以下這樣囉：

def dfs(ss):
    if ss in dic:
        return True
    dic[ss] = 1
    if len(ss) == l:
        if ss not in existStr:
            print(ss)
            return False
        return True
    for i in k:
        if dfs(ss+i) == False:
            return False

k = list(input())
l = int(input())
s = input()

existStr = set(s[i:i+l] for i in range(len(s) - l + 1))
dic = {}
dfs("" )

我把剪枝(用來加速)的部分標藍色，基本上這題不剪枝，也不會超時，非常佛心呢。