构造有效字符串的最少插入数
难度:
标签:
题目描述
Given a string word to which you can insert letters "a", "b" or "c" anywhere and any number of times, return the minimum number of letters that must be inserted so that word becomes valid.
A string is called valid if it can be formed by concatenating the string "abc" several times.
Example 1:
Input: word = "b" Output: 2 Explanation: Insert the letter "a" right before "b", and the letter "c" right next to "a" to obtain the valid string "abc".
Example 2:
Input: word = "aaa" Output: 6 Explanation: Insert letters "b" and "c" next to each "a" to obtain the valid string "abcabcabc".
Example 3:
Input: word = "abc" Output: 0 Explanation: word is already valid. No modifications are needed.
Constraints:
1 <= word.length <= 50wordconsists of letters "a", "b" and "c" only.
代码结果
运行时间: 24 ms, 内存: 16.5 MB
/*
题目思路：
使用 Java Stream 可以通过减少代码的冗余，更加简洁地解决问题。
我们可以将字符串按顺序分割为三个部分，然后分别统计缺少的字符数。
1. 按顺序将字符串拆分成三部分：a、b、c。
2. 统计每部分字符的个数。
3. 计算插入字符数的最小值。
*/
import java.util.stream.IntStream;
public class Solution {
public int addMinimum(String word) {
int[] count = {0, 0, 0};
int[] target = {'a', 'b', 'c'};
IntStream.range(0, word.length()).forEach(i -> {
if (word.charAt(i) == 'a') count[0]++;
else if (word.charAt(i) == 'b') count[1]++;
else if (word.charAt(i) == 'c') count[2]++;
});
int insertCount = 0;
insertCount += Math.max(0, count[1] - count[0]);
insertCount += Math.max(0, count[2] - count[1]);
return insertCount;
}
}解释
方法:
题解的核心思路是检查给定字符串并确定需要补充多少个字符来使其成为有效的 'abc' 序列。初始的时候，比较字符串的第一个字符和最后一个字符，以决定在字符串首尾可能需要添加的字符数量。然后，遍历字符串中相邻的字符，计算两个字符之间可能需要插入的字符数。这是通过将每个字符转换为其 ASCII 值，计算差值并根据差值来决定插入的字符数量。具体来说，采用模3运算来确定需要插入的字符数，因为 'abc' 三个字符在循环中可以形成闭环。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
解法中提到的'将每个字符转换为其ASCII值，计算差值并根据差值来决定插入的字符数量'，请问这个差值是怎样反映字符之间缺失的'abc'序列的？
▷🦆
在考虑首尾字符时，为什么将`ord(s[0]) - ord(s[-1]) + 2`作为需要添加的字符数量？这个公式背后的逻辑是什么？
▷🦆
题解中使用了`(y - x + 2) % 3`来计算需要插入的字符数量，为什么要加2而不是其他数字？这样做的目的是什么？
▷