网站建设课程总结,初中作文优秀作文,百度广告竞价,wordpress小程序推荐题目
2645. 构造有效字符串的最少插入数
给你一个字符串 word #xff0c;你可以向其中任何位置插入 “a”、“b” 或 “c” 任意次#xff0c;返回使 word 有效 需要插入的最少字母数。
如果字符串可以由 “abc” 串联多次得到#xff0c;则认为该字符串 有效 。
示例 …题目
2645. 构造有效字符串的最少插入数
给你一个字符串 word 你可以向其中任何位置插入 “a”、“b” 或 “c” 任意次返回使 word 有效 需要插入的最少字母数。
如果字符串可以由 “abc” 串联多次得到则认为该字符串 有效 。
示例 1
输入word b
输出2
解释在 b 之前插入 a 在 b 之后插入 c 可以得到有效字符串 abc 。示例 2
输入word aaa
输出6
解释在每个 a 之后依次插入 b 和 c 可以得到有效字符串 abcabcabc 。示例 3
输入word abc
输出0
解释word 已经是有效字符串不需要进行修改。 提示
1 word.length 50word 仅由字母 “a”、“b” 和 “c” 组成。
分析
当我们匹配到某个字符word[i]最大增加2个字符即可形成新“abc对与i1个字符如果wordp[i1]word[i] 那么实际上只需要增加1个字符例如ab ac bc 假设原本加上了2现在需要减1最多会被减2次假设字符的增连续3个字符之后必然不会是单调的因为word 仅由字母 “a”、“b” 和 “c” 组成。用res表示总的需要增加的字符所以对于每个字符i 如果chs[i]chs[i-1] 实际上只需要增加1个字符 res减一其他情况res加2
编码
class Solution {public int addMinimum(String word) {int res 2;char [] chs word.toCharArray();for (int i 1; i chs.length; i) {if(chs[i]chs[i-1]) res--;else res2;}return res;}}复杂度
时间复杂度O(N)
空间复杂度O(1)
交流
