2645. 构造有效字符串的最少插入数

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 已经是有效字符串，不需要进行修改。

/src/leetcode

1 <= word.length <= 50

word 仅由字母 "a"、"b" 和 "c" 组成。

代码

代码中 1~3 逐渐简化。

javascript

// 2645. 构造有效字符串的最少插入数
// https://leetcode.cn/problems/minimum-additions-to-make-valid-string/description/

export function addMinimum1(word) {
  const start = 'a'.charCodeAt(0)
  const end = 'c'.charCodeAt(0)
  let res = 0
  for (let index = 0; index < word.length; index++) {
    if (index === 0 || index === word.length - 1) {
      // 单个的时候需要前后两次执行
      if (index === 0) {
        res += word.charCodeAt(index) - start
      }
      if (index === word.length - 1) {
        if (index - 1 >= 0) res += (word.charCodeAt(index) - word.charCodeAt(index - 1) - 1 + 3) % 3
        res += end - word.charCodeAt(index)
      }
    } else {
      res += (word.charCodeAt(index) - word.charCodeAt(index - 1) - 1 + 3) % 3
    }
  }
  return res
};

export function addMinimum2(word) {
  const start = 'a'.charCodeAt(0)
  const end = 'c'.charCodeAt(0)
  let res = 0
  for (let index = 0; index < word.length; index++) {
    if (index === 0) {
      // 前后合并
      res += word.charCodeAt(index) - word.charCodeAt(word.length - 1) + end - start
    } else {
      res += (word.charCodeAt(index) - word.charCodeAt(index - 1) - 1 + 3) % 3
    }
  }
  return res
};

export function addMinimum3(word) {
  // 前后提取出来，其余的遍历
  let res = word.charCodeAt(0) - word.charCodeAt(word.length - 1) + 2
  for (let index = 1; index < word.length; index++) {
    res += (word.charCodeAt(index) - word.charCodeAt(index - 1) - 1 + 3) % 3
  }
  return res
};

typescript

// 2645. 构造有效字符串的最少插入数
// https://leetcode.cn/problems/minimum-additions-to-make-valid-string/description/

export function addMinimum1(word: string): number {
  const start = 'a'.charCodeAt(0)
  const end = 'c'.charCodeAt(0)
  let res = 0
  for (let index = 0; index < word.length; index++) {
    if (index === 0 || index === word.length - 1) {
      // 单个的时候需要前后两次执行
      if (index === 0) {
        res += word.charCodeAt(index) - start
      }
      if (index === word.length - 1) {
        if (index - 1 >= 0) res += (word.charCodeAt(index) - word.charCodeAt(index - 1) - 1 + 3) % 3
        res += end - word.charCodeAt(index)
      }
    } else {
      res += (word.charCodeAt(index) - word.charCodeAt(index - 1) - 1 + 3) % 3
    }
  }
  return res
};

export function addMinimum2(word: string): number {
  const start = 'a'.charCodeAt(0)
  const end = 'c'.charCodeAt(0)
  let res = 0
  for (let index = 0; index < word.length; index++) {
    if (index === 0) {
      // 前后合并
      res += word.charCodeAt(index) - word.charCodeAt(word.length - 1) + end - start
    } else {
      res += (word.charCodeAt(index) - word.charCodeAt(index - 1) - 1 + 3) % 3
    }
  }
  return res
};

export function addMinimum3(word: string): number {
  // 前后提取出来，其余的遍历
  let res = word.charCodeAt(0) - word.charCodeAt(word.length - 1) + 2
  for (let index = 1; index < word.length; index++) {
    res += (word.charCodeAt(index) - word.charCodeAt(index - 1) - 1 + 3) % 3
  }
  return res
};

测试代码

test

import { expect, test } from 'vitest'
import { addMinimum1, addMinimum2, addMinimum3 } from './typescript.ts'
import { addMinimum1 as addMinimum1Js, addMinimum2 as addMinimum2Js, addMinimum3 as addMinimum3Js } from './javascript.js'

test(`addMinimum1('a') toBe 2`, () => {
  expect(addMinimum1('a')).toBe(2)
})

test(`addMinimum1('aaa') toBe 6`, () => {
  expect(addMinimum1('aaa')).toBe(6)
})

test(`addMinimum1('abc') toBe 0`, () => {
  expect(addMinimum1('abc')).toBe(0)
})


test(`addMinimum2('a') toBe 2`, () => {
  expect(addMinimum2('a')).toBe(2)
})

test(`addMinimum2('aaa') toBe 6`, () => {
  expect(addMinimum2('aaa')).toBe(6)
})

test(`addMinimum2('abc') toBe 0`, () => {
  expect(addMinimum2('abc')).toBe(0)
})


test(`addMinimum3('a') toBe 2`, () => {
  expect(addMinimum3('a')).toBe(2)
})

test(`addMinimum3('aaa') toBe 6`, () => {
  expect(addMinimum3('aaa')).toBe(6)
})

test(`addMinimum3('abc') toBe 0`, () => {
  expect(addMinimum3('abc')).toBe(0)
})


test(`addMinimum1Js('a') toBe 2`, () => {
  expect(addMinimum1Js('a')).toBe(2)
})

test(`addMinimum1Js('aaa') toBe 6`, () => {
  expect(addMinimum1Js('aaa')).toBe(6)
})

test(`addMinimum1Js('abc') toBe 0`, () => {
  expect(addMinimum1Js('abc')).toBe(0)
})


test(`addMinimum2Js('a') toBe 2`, () => {
  expect(addMinimum2Js('a')).toBe(2)
})

test(`addMinimum2Js('aaa') toBe 6`, () => {
  expect(addMinimum2Js('aaa')).toBe(6)
})

test(`addMinimum2Js('abc') toBe 0`, () => {
  expect(addMinimum2Js('abc')).toBe(0)
})


test(`addMinimum3Js('a') toBe 2`, () => {
  expect(addMinimum3Js('a')).toBe(2)
})

test(`addMinimum3Js('aaa') toBe 6`, () => {
  expect(addMinimum3Js('aaa')).toBe(6)
})

test(`addMinimum3Js('abc') toBe 0`, () => {
  expect(addMinimum3Js('abc')).toBe(0)
})