本題敘述:
給定一個大小為 K 個字母的集合和字串 S,求出在使用該集合所組出長度為 L 字串中,不為字串 S 子字串的最小字典序字串為何。
例如字母集合 {a,c,m},其能組出長度為 2 的字串字典序由小到大排序為 aa < ac < am < ca < cc < cm < ma < mc < mm。字串 S 為 accaamcm,因此 ma 為不在 S 內的最小字典序字串。
def generate_strings(letters, length, current_string, all_strings):
if length == 0:
all_strings.append(current_string)
return
for letter in letters:
generate_strings(letters, length - 1, current_string + letter, all_strings)
letters = list(input())
L = int(input())
S = input()
all_strings = []
generate_strings(letters, L, "", all_strings)
for string in all_strings:
if string not in S:
print(string)
break
def generate_strings(letters, length, current_string, all_strings):
if length == 0:
all_strings.append(current_string)
return
for letter in letters:
generate_strings(letters, length - 1, current_string + letter, all_strings)
這是一個遞迴函數,用於生成給定字母集合中所有特定長度的字符串。這裡的具體步驟如下:
假設 letters = ['a', 'b']
和 length = 2
,這段代碼會生成所有長度為2的字符串:
初始調用:generate_strings(['a', 'b'], 2, "", all_strings)
length
不為0,進入循環:letters
,第一個字符是 'a',調用 generate_strings(['a', 'b'], 1, "a", all_strings)
第二次調用:generate_strings(['a', 'b'], 1, "a", all_strings)
length
不為0,進入循環:letters
,第一個字符是 'a',調用 generate_strings(['a', 'b'], 0, "aa", all_strings)
第三次調用:generate_strings(['a', 'b'], 0, "aa", all_strings)
length
為0,將 "aa" 添加到 all_strings
中,返回上一層回到第二次調用,繼續循環:
generate_strings(['a', 'b'], 0, "ab", all_strings)
第四次調用:generate_strings(['a', 'b'], 0, "ab", all_strings)
length
為0,將 "ab" 添加到 all_strings
中,返回上一層如此反覆,最終會生成所有長度為2的字符串:"aa", "ab", "ba", "bb"。這些字符串會被依次添加到 all_strings
中。
本題知識:
def generate_strings(letters, length, current_string, existing_strings):
if length == 0:
if current_string not in existing_strings:
print(current_string)
return True
return False
for letter in letters:
if generate_strings(letters, length - 1, current_string + letter, existing_strings):
return True
return False
letters = list(input())
L = int(input())
S = input()
# 使用Set來提升查找效率
existing_strings = set(S[i:i+L] for i in range(len(S) - L + 1))
generate_strings(letters, L, "", existing_strings)