README_EN.md

comments	difficulty	edit_url	rating	source	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/3300-3399/3324.Find%20the%20Sequence%20of%20Strings%20Appeared%20on%20the%20Screen/README_EN.md	1293	Weekly Contest 420 Q1	String Simulation

3324. Find the Sequence of Strings Appeared on the Screen

中文文档

Description

You are given a string target.

Alice is going to type target on her computer using a special keyboard that has only two keys:

• Key 1 appends the character "a" to the string on the screen.
• Key 2 changes the last character of the string on the screen to its next character in the English alphabet. For example, "c" changes to "d" and "z" changes to "a".

Note that initially there is an empty string "" on the screen, so she can only press key 1.

Return a list of all strings that appear on the screen as Alice types target, in the order they appear, using the minimum key presses.

 

Example 1:

Input: target = "abc"

Output: ["a","aa","ab","aba","abb","abc"]

Explanation:

The sequence of key presses done by Alice are:

• Press key 1, and the string on the screen becomes "a".
• Press key 1, and the string on the screen becomes "aa".
• Press key 2, and the string on the screen becomes "ab".
• Press key 1, and the string on the screen becomes "aba".
• Press key 2, and the string on the screen becomes "abb".
• Press key 2, and the string on the screen becomes "abc".

Example 2:

Input: target = "he"

Output: ["a","b","c","d","e","f","g","h","ha","hb","hc","hd","he"]

 

Constraints:

• 1 <= target.length <= 400
• target consists only of lowercase English letters.

Solutions

Solution 1: Simulation

We can simulate Alice's typing process, starting from an empty string and updating the string after each keystroke until the target string is obtained.

The time complexity is $O(n^2 \times |\Sigma|)$, where $n$ is the length of the target string and $\Sigma$ is the character set, which in this case is the set of lowercase letters, so $|\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;
}