3324. 出现在屏幕上的字符串序列

题目描述

给你一个字符串 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 <= 400
target 仅由小写英文字母组成。

解法

方法一：模拟

我们可以模拟 Alice 按键的过程，从空字符串开始，每次按键后更新字符串，直到得到目标字符串。

时间复杂度 $O(n^2 \times |\Sigma|)$，其中 $n$ 是目标字符串的长度，而 $\Sigma$ 是字符集，这里是小写字母集合，因此 $|\Sigma| = 26$。

Python3JavaC++GoTypeScript

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

class Solution {
    public List<String> stringSequence(String target) {
        List<String> ans = new ArrayList<>();
        for (char c : target.toCharArray()) {
            String s = ans.isEmpty() ? "" : ans.get(ans.size() - 1);
            for (char a = 'a'; a <= c; ++a) {
                String t = s + a;
                ans.add(t);
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<string> stringSequence(string target) {
        vector<string> ans;
        for (char c : target) {
            string s = ans.empty() ? "" : ans.back();
            for (char a = 'a'; a <= c; ++a) {
                string t = s + a;
                ans.push_back(t);
            }
        }
        return ans;
    }
};

func stringSequence(target string) (ans []string) {
    for _, c := range target {
        s := ""
        if len(ans) > 0 {
            s = ans[len(ans)-1]
        }
        for a := 'a'; a <= c; a++ {
            t := s + string(a)
            ans = append(ans, t)
        }
    }
    return
}

function stringSequence(target: string): string[] {
    const ans: string[] = [];
    for (const c of target) {
        let s = ans.length > 0 ? ans[ans.length - 1] : '';
        for (let a = 'a'.charCodeAt(0); a <= c.charCodeAt(0); a++) {
            const t = s + String.fromCharCode(a);
            ans.push(t);
        }
    }
    return ans;
}

3324. 出现在屏幕上的字符串序列

题目描述

解法

方法一：模拟

评论