当前位置：首页 > article >正文

力扣第 420 场周赛 3324. 出现在屏幕上的字符串序列

article 2024/10/27 2:06:59

一、题目

在这里插入图片描述

二、思路

由于操作只有两种：

按键1：追加 ‘a’
按键2：依次递增变更字母，如当前字母为’b’，按一次按键2，将当前字母变更为 ‘c’。
最初的字符串是空串，所以每次都从 ‘a’ 开始进行依次改变，直至和 target 的对应位变为相同的字符。也正因为是从 ‘a’ 开始变更的，所以从 ‘a’ 变为目标字符的过程就是按键次数最少的过程，不需要考虑题目中所说的 ‘z’ 变为 ‘a’。另外，将每次添加或是变更字母过程中产生的新的字符串都要添加到输出的列表中。

三、代码

解法1：

class Solution {
    public List<String> stringSequence(String target) {
        List<String> ans = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        path.append('a');
        ans.add(path.toString());
        int n = target.length();
        for (int i = 0; i < n; i++) {
        	// 计算需要按按键2的次数 move
            int move = target.charAt(i) - path.charAt(i);
            // 将 path 的第 i 位依次更改为 target 的第 i 位
            for (int j = 0; j < move; j++) {
                char nxtChar = (char)(path.charAt(i) + 1);
                path.setCharAt(i, nxtChar);
                ans.add(path.toString());
            }
            // path 字符个数小于 target 字符个数就继续追加 'a'
            if (i < n - 1) {
                path.append('a');
                ans.add(path.toString());
            }
        }
        return ans;
    }
}

解法2：将 target 转换为 char Array

class Solution {
    public List<String> stringSequence(String target) {
        List<String> ans = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        for (char c : target.toCharArray()) {
            path.append('a');
            for (char i = 'a'; i <= c; i++) {
                path.setCharAt(path.length() - 1, i);
                ans.add(path.toString());
            }
        }
        return ans;
    }
}