Medium

题目描述

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

解题思路

这道题需要模拟键盘输入的过程，分析输入策略可以发现：

核心思路：

  1. 对于目标字符串的每个位置，我们都需要先添加字符 ‘a’（按键1），然后通过按键2将其转换为目标字符
  2. 按键2是循环的：‘a’→‘b’→…→‘z’→‘a’

算法步骤：

  1. 初始化结果数组和当前字符串
  2. 对于目标字符串的每个字符：
    • 先添加 ‘a’ 到当前字符串（模拟按键1）
    • 记录这个状态到结果中
    • 然后不断按键2，将最后一个字符从 ‘a’ 转换到目标字符
    • 每次转换都记录当前状态
  3. 重复直到处理完所有字符

时间复杂度分析：

  • 最坏情况下，每个字符需要从 ‘a’ 转换到 ‘z’，需要25次按键2
  • 总体时间复杂度为 O(n × 26)，其中 n 是目标字符串长度

这是一道纯模拟题，关键是理解输入策略：总是先添加 ‘a’，再通过按键2逐步转换到目标字符。

代码实现

class Solution {
public:
    vector<string> stringSequence(string target) {
        vector<string> result;
        string current = "";
        
        for (char c : target) {
            current += 'a';  // 按键1：添加字符'a'
            result.push_back(current);
            
            // 按键2：将最后一个字符转换为目标字符
            while (current.back() != c) {
                current.back() = (current.back() == 'z') ? 'a' : current.back() + 1;
                result.push_back(current);
            }
        }
        
        return result;
    }
};

class Solution:
    def stringSequence(self, target: str) -> List[str]:
        result = []
        current = ""
        
        for c in target:
            current += 'a'  # 按键1：添加字符'a'
            result.append(current)
            
            # 按键2：将最后一个字符转换为目标字符
            while current[-1] != c:
                last_char = current[-1]
                next_char = 'a' if last_char == 'z' else chr(ord(last_char) + 1)
                current = current[:-1] + next_char
                result.append(current)
        
        return result

public class Solution {
    public IList<string> StringSequence(string target) {
        IList<string> result = new List<string>();
        StringBuilder current = new StringBuilder();
        
        foreach (char c in target) {
            current.Append('a');  // 按键1：添加字符'a'
            result.Add(current.ToString());
            
            // 按键2：将最后一个字符转换为目标字符
            while (current[current.Length - 1] != c) {
                char lastChar = current[current.Length - 1];
                char nextChar = (lastChar == 'z') ? 'a' : (char)(lastChar + 1);
                current[current.Length - 1] = nextChar;
                result.Add(current.ToString());
            }
        }
        
        return result;
    }
}

/**
 * @param {string} target
 * @return {string[]}
 */
var stringSequence = function(target) {
    const result = [];
    let current = "";
    
    for (let i = 0; i < target.length; i++) {
        // Add 'a' to current string
        current += 'a';
        result.push(current);
        
        // Change last character until it matches target[i]
        while (current[current.length - 1] !== target[i]) {
            let lastChar = current[current.length - 1];
            let nextChar = lastChar === 'z' ? 'a' : String.fromCharCode(lastChar.charCodeAt(0) + 1);
            current = current.slice(0, -1) + nextChar;
            result.push(current);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × 26)，其中 n 是目标字符串长度，每个字符最多需要26次按键操作
空间复杂度O(k)，其中 k 是结果数组的大小，最坏情况下为 O(n × 26)

相关题目