# **APCS Jun 2024 - o078 [Q3](https://zerojudge.tw/ShowProblem?problemid=o078) [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)

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