LeetCode 1328. 破坏回文串

Categories:

题目描述
思路分析
1. 解法一：贪心修改（推荐）
相似题目

题目描述

✅ 1328. 破坏回文串

思路分析

解法一：贪心修改（推荐）

核心思路：

若长度为 1，无法得到非回文串，返回空串。

在前半段找第一个不是 'a' 的字符改成 'a'，使字典序最小。

若前半段全是 'a'，则把最后一个字符改成 'b'。

复杂度分析：

时间复杂度：O(n)，其中 n 为字符串长度。

空间复杂度：O(n)，转为字符数组处理。

class Solution {
    public String breakPalindrome(String palindrome) {
        int n = palindrome.length();
        if (n == 1) {
            return "";
        }

        char[] arr = palindrome.toCharArray();
        for (int i = 0; i < n / 2; i++) {
            if (arr[i] != 'a') {
                arr[i] = 'a';
                return new String(arr);
            }
        }
        arr[n - 1] = 'b';
        return new String(arr);
    }
}

func breakPalindrome(palindrome string) string {
    n := len(palindrome)
    if n == 1 {
        return ""
    }

    arr := []byte(palindrome)
    for i := 0; i < n/2; i++ {
        if arr[i] != 'a' {
            arr[i] = 'a'
            return string(arr)
        }
    }
    arr[n-1] = 'b'
    return string(arr)
}

相似题目

题目	难度	考察点
409. 最长回文串	简单	贪心
680. 验证回文串 II	简单	双指针
647. 回文子串	中等	回文
516. 最长回文子序列	中等	DP
1312. 让字符串成为回文串的最少插入次数	困难	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/13822327