You are given a string target.
Alice is going to type target on her computer using a special keyboard that has only two keys:
"a" to the string on the screen."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:
"a"."aa"."ab"."aba"."abb"."abc".Example 2:
Input: target = "he"
Output: ["a","b","c","d","e","f","g","h","ha","hb","hc","hd","he"]
Constraints:
1 <= target.length <= 400target consists only of lowercase English letters.This approach involves simulating each key press step by step. Begin with an empty string and use Key 1 to add characters or Key 2 to change the last character until the target is achieved.
Iteratively compare each target character with the current screen character to decide whether to append or modify with Key 2.
In this C implementation, we simulate each step by maintaining a string current that represents the content on the screen at any time.
For each step, we append 'a' using Key 1 and subsequently change the character to match the target using Key 2.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * 26), where n is the length of the string because, for each character, in the worst case, you might need to press Key 2 up to 26 times.
Space Complexity: O(n^2) for storing the intermediate strings.
An optimized approach focuses on noticing that each time Key 1 is used, it adds 'a', and any further changes with Key 2 depends on the target character. Thus, compute the difference directly and assemble the sequence more directly without individually adding each character.
This C implementation manually computes the letter transformation count by directly evaluating character differences.
This adjusts string states more directly and concisely.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) per string, focusing directly on character differences.
Space Complexity: O(n^2) as still recording multiple states.
| Approach | Complexity |
|---|---|
| Iterative String Construction | Time Complexity: Space Complexity: |
| Optimized Approach with Direct Character Manipulation | Time Complexity: Space Complexity: |
Group Anagrams - Categorize Strings by Count - Leetcode 49 • NeetCode • 611,591 views views
Watch 9 more video solutions →Practice Find the Sequence of Strings Appeared on the Screen with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor