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

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

• 难度: medium
• 原始链接: https://leetcode.cn/problems/minimum-additions-to-make-valid-string
• 标签: 动态规划, 模拟

解法一: 模拟

go

func addMinimum(word string) int {
    insertList := [][]int{
        {2, 0, 1},
        {1, 2, 0},
        {0, 1, 2},
    }
    word += "a"
    pre := 'c'
    ans := 0
    for _, ch := range word {
        ans += insertList[pre - 'a'][ch - 'a']
        pre = ch
    }
    return ans
}

解法二: 动态规划

java

class Solution {
    public int addMinimum(String word) {
        int n = word.length();
        int[] dp = new int[n + 1];
        for (int i = 0; i < n; i++) {
            dp[i + 1] = dp[i] + 2;
            if (i > 0 && word.charAt(i) > word.charAt(i - 1)) {
                dp[i + 1] = dp[i] - 1;
            }
        }
        return dp[n];
    }
}

解法三: 计数组数

java

class Solution {
    public int addMinimum(String word) {
        int n = word.length();
        int count = 1;
        for (int i = 1; i < n; i++) {
            if (word.charAt(i) <= word.charAt(i - 1)) {
                count++;
            }
        }
        return count * 3 - n;
    }
}