回到文章

APCS Jun 2024 - o078


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協作,若有錯誤請備註。

image


其實還可以更快:

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)

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

image