Skip to content

Latest commit

 

History

History
180 lines (137 loc) · 4.9 KB

README.md

File metadata and controls

180 lines (137 loc) · 4.9 KB
comments difficulty edit_url rating source tags
true
中等
1293
第 420 场周赛 Q1
字符串
模拟

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

English Version

题目描述

给你一个字符串 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$。

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}