题目描述

给你一个字符串 target。

Alice 将会使用一种特殊的键盘在她的电脑上输入 target，这个键盘 只有两个 按键：

• 按键 1：在屏幕上的字符串后追加字符 'a'。
• 按键 2：将屏幕上字符串的 最后一个 字符更改为英文字母表中的 下一个 字符。例如，'c' 变为 'd'，'z' 变为 'a'。

注意，最初屏幕上是一个空字符串 ""，所以她 只能 按按键 1。

请你考虑按键次数 最少 的情况，按字符串出现顺序，返回 Alice 输入 target 时屏幕上出现的所有字符串列表。

样例

输入： target = "abc"

输出： ["a","aa","ab","aba","abb","abc"]

解释：

Alice 按键的顺序如下：

按下按键 1，屏幕上的字符串变为 "a"。
按下按键 1，屏幕上的字符串变为 "aa"。
按下按键 2，屏幕上的字符串变为 "ab"。
按下按键 1，屏幕上的字符串变为 "aba"。
按下按键 2，屏幕上的字符串变为 "abb"。
按下按键 2，屏幕上的字符串变为 "abc"。

输入： target = "he"

输出： ["a","b","c","d","e","f","g","h","ha","hb","hc","hd","he"]

限制

• 1 <= target.length <= 400
• target 仅由小写英文字母组成。

算法

(模拟) $O(n |\Sigma|)$

1. 按照题意进行模拟。
2. 遍历原字符串，同时维护一个当前的字符串。
3. 遍历时，每次增加一个新的字符 a，然后将新增加的字符逐步变为当前遍历到的字符。同时，在循环的过程中，将当前字符串不断插入到答案数组中。

时间复杂度

• 每次增加新字符都需要 $O(|\Sigma|)$ 的时间，故总时间复杂度为 $O(n |\Sigma|)$。

空间复杂度

• 需要 $O(n |\Sigma|)$ 的额外空间存储答案。

C++ 代码

class Solution {
public:
    vector<string> stringSequence(string target) {
        vector<string> ans;

        string cur;
        for (char c : target) {
            cur += "a";
            ans.push_back(cur);

            while (cur.back() != c) {
                ++cur.back();
                ans.push_back(cur);
            }
        }

        return ans;
    }
};