问题描述

小D拿到了一个仅由 "abc" 三种字母组成的字符串。她每次操作会对所有字符同时进行以下变换：

• 将 'a' 变成 'bc'
• 将 'b' 变成 'ca'
• 将 'c' 变成 'ab'

小D将重复该操作 k 次。你的任务是输出经过 k 次变换后，得到的最终字符串。

例如：对于初始字符串 "abc"，执行 2 次操作后，字符串将变为 "caababbcbcca"。

测试样例

样例1：

输入：s = "abc", k = 2
输出：'caababbcbcca'

样例2：

输入：s = "abca", k = 3
输出：'abbcbccabccacaabcaababbcabbcbcca'

样例3：

输入：s = "cba", k = 1
输出：'abcabc'

 

解题思路：

很基础的模拟题

问题理解

你有一个仅由 'a', 'b', 'c' 组成的字符串 s，并且你需要对这个字符串进行 k 次变换。每次变换的规则如下：

• 'a' 变成 'bc'
• 'b' 变成 'ca'
• 'c' 变成 'ab'

数据结构选择

由于每次变换都会使字符串的长度增加，直接模拟这个过程可能会导致内存和时间上的问题，尤其是当 k 很大时。因此，我们需要找到一种更高效的方法来处理这个问题。

算法步骤

1. 直接模拟：对于较小的 k，可以直接模拟每次变换的过程。
2. 周期性分析：观察变换的周期性，可能会发现某些模式或周期性，从而减少计算量。

最后跑的时候发现用例的k值和字符串其实都特别小，这个特判不管处不处理都能AC

最终代码：

def transform(s):result = ""for c in s:if c == 'a':result += "bc"elif c == 'b':result += "ca"elif c == 'c':result += "ab"return resultdef solution(s, k):# 如果 k 较小，直接模拟变换if k <= 5:for _ in range(k):s = transform(s)return s# 如果 k 较大，尝试寻找周期性seen = {s: 0}# 进行变换并检查周期性for i in range(1, k + 1):s = transform(s)# 检查是否出现了重复的模式if s in seen:# 找到周期性cycle_start = seen[s]cycle_length = i - cycle_start# 计算剩余的变换次数remaining_k = (k - cycle_start) % cycle_length# 进行剩余的变换for _ in range(remaining_k):s = transform(s)return s# 记录当前变换结果seen[s] = ireturn s# 测试样例
print(solution("abc", 2) == "caababbcbcca")
print(solution("abca", 3) == "abbcbccabccacaabcaababbcabbcbcca")
print(solution("cba", 1) == "abcabc")

 运行结果：