APCS Jun 2024 - o078 Q3 [Python]

本題敘述：

給定一個大小為 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

---

解題報告：

1. 遞迴

   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的字符串：

     1. 初始調用：generate_strings(['a', 'b'], 2, "", all_strings)

        • length 不為0，進入循環：
        • 迴圈中的 letters，第一個字符是 'a'，調用 generate_strings(['a', 'b'], 1, "a", all_strings)

     2. 第二次調用：generate_strings(['a', 'b'], 1, "a", all_strings)

        • length 不為0，進入循環：
        • 迴圈中的 letters，第一個字符是 'a'，調用 generate_strings(['a', 'b'], 0, "aa", all_strings)

     3. 第三次調用：generate_strings(['a', 'b'], 0, "aa", all_strings)

        • length 為0，將 "aa" 添加到 all_strings 中，返回上一層

     4. 回到第二次調用，繼續循環：

        • 第二個字符是 'b'，調用 generate_strings(['a', 'b'], 0, "ab", all_strings)

     5. 第四次調用：generate_strings(['a', 'b'], 0, "ab", all_strings)

        • length 為0，將 "ab" 添加到 all_strings 中，返回上一層

     如此反覆，最終會生成所有長度為2的字符串："aa", "ab", "ba", "bb"。這些字符串會被依次添加到 all_strings 中。

本題知識：

• 遞迴

---

• [✔️] 程式碼如果需要可以直接使用。
• [✔️] 分享貼文請標註來源。
• [✔️] 此文章解題報告為AI協作，若有錯誤請備註。

---

其實還可以更快：

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)

• 語文能力不足請自行理解:)。