Re: [閒聊] 每日LeetCode
1328. Break a Palindrome
給定一個迴文字串palindrome，返回取代palindrome中恰好一字元，使其變為迴文
的「最小」字串。
Example：
abccba可以有多種方法取代一個字串使他是非迴文：
zbccba
aaccba
但是我們要求「最小」的（zb > aa），所以取第二個當解。
Example：
Input: palindrome = "a"
Output: ""
Explanation：不能變非迴文就返回空字符串
思路：
1.若輸入字串長度為1則怎麼替換他都是迴文，返回空字符串。
2.對替代字符串貪婪，我們先掃描字串的前半部份，若任意字元不是a則將他替換為a
必定是最小字串，替換掉後直接返回。
3.若前面的一半字串都是a，這個字串只可能是奇數長度的下列字串：
aaaaaxaaaaa
把最後一個字串替換掉成「b」即是最小非迴文字串
aaaaaxaaaab
Java Code：
class Solution {
public String breakPalindrome(String palindrome) {
char[] str = palindrome.toCharArray();
int n = str.length;
if(n == 1) return "";
for(int i = 0;i < n/2;i++) {
if(str[i] != 'a') {
str[i] = 'a';
return new String(str);
}
}
str[n - 1] = 'b';
return new String(str);
}
}
https://i.imgur.com/zvHxGhl.png
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.111.108 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1665383889.A.464.html
推
10/10 14:45,
1年前
, 1F
10/10 14:45, 1F
※ 編輯: Rushia (49.159.111.108 臺灣), 10/10/2022 14:47:06
→
10/10 14:46,
1年前
, 2F
10/10 14:46, 2F
討論串 (同標題文章)
完整討論串 (本文為第 41 之 719 篇)：
閒聊
1
3