LeetCode 题解工作台
出现在屏幕上的字符串序列
给你一个字符串 target 。 Alice 将会使用一种特殊的键盘在她的电脑上输入 target ，这个键盘 只有两个 按键： 按键 1：在屏幕上的字符串后追加字符 'a' 。 按键 2：将屏幕上字符串的 最后一个 字符更改为英文字母表中的 下一个 字符。例如， 'c' 变为 'd' ， 'z' …
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · string·结合·模拟
答案摘要
我们可以模拟 Alice 按键的过程，从空字符串开始，每次按键后更新字符串，直到得到目标字符串。 时间复杂度 $O(n^2 \times |\Sigma|)$，其中 是目标字符串的长度，而 是字符集，这里是小写字母集合，因此 $|\Sigma| = 26$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 string·结合·模拟 题型思路
题目描述
给你一个字符串 target。
Alice 将会使用一种特殊的键盘在她的电脑上输入 target，这个键盘 只有两个 按键：
- 按键 1：在屏幕上的字符串后追加字符
'a'。 - 按键 2：将屏幕上字符串的 最后一个 字符更改为英文字母表中的 下一个 字符。例如，
'c'变为'd'，'z'变为'a'。
注意，最初屏幕上是一个空字符串 ""，所以她 只能 按按键 1。
请你考虑按键次数 最少 的情况，按字符串出现顺序，返回 Alice 输入 target 时屏幕上出现的所有字符串列表。
示例 1：
输入： target = "abc"
输出： ["a","aa","ab","aba","abb","abc"]
解释：
Alice 按键的顺序如下：
- 按下按键 1，屏幕上的字符串变为
"a"。 - 按下按键 1，屏幕上的字符串变为
"aa"。 - 按下按键 2，屏幕上的字符串变为
"ab"。 - 按下按键 1，屏幕上的字符串变为
"aba"。 - 按下按键 2，屏幕上的字符串变为
"abb"。 - 按下按键 2，屏幕上的字符串变为
"abc"。
示例 2：
输入： target = "he"
输出： ["a","b","c","d","e","f","g","h","ha","hb","hc","hd","he"]
提示：
1 <= target.length <= 400target仅由小写英文字母组成。
解题思路
方法一：模拟
我们可以模拟 Alice 按键的过程，从空字符串开始，每次按键后更新字符串，直到得到目标字符串。
时间复杂度 ，其中 是目标字符串的长度，而 是字符集，这里是小写字母集合，因此 。
class Solution:
def stringSequence(self, target: str) -> List[str]:
ans = []
for c in target:
s = ans[-1] if ans else ""
for a in ascii_lowercase:
t = s + a
ans.append(t)
if a == c:
break
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate understands string manipulation and simulation patterns.
- question_mark
The candidate demonstrates an ability to break down problems into small, manageable steps.
- question_mark
The candidate shows good understanding of how to optimize repeated operations.
常见陷阱
外企场景- error
Forgetting to track intermediate steps in the sequence.
- error
Not handling the case where key 2 appends the current string properly.
- error
Using inefficient string operations that lead to poor performance.
进阶变体
外企场景- arrow_right_alt
Optimize the simulation using dynamic programming to improve time complexity.
- arrow_right_alt
Consider varying the keyboard functionality, e.g., introducing more keys.
- arrow_right_alt
Extend the problem to support strings with different character sets.