問題：
給定 ascii[az] 范圍內的一串小寫字母，確定要洗掉的字符索引以將字串更改為回文。如果字串無法轉換為回文或已經是回文，則回傳 -1 否則回傳要洗掉的字符的索引。
我的解決方案：
public static int palindromeIndex(String s) {
if(p(s)){
return -1;
}
StringBuilder sb = new StringBuilder(s);
for(int i=0; i<s.length(); i ){
sb.deleteCharAt(i);
if(p(sb.toString())){
return i;
}
sb.insert(i,s.charAt(i));
}
return -1;
}
private static boolean p(String s){
for(int i=0; i<s.length()/2; i ){
if(s.charAt(i) != s.charAt(s.length() - i - 1)){
return false;
}
}
return true;
}
根據hackerrank，以下一個或所有測驗用例（無法確定哪個）失敗：
- quyjjdcgsvvsgcdjjyq
- hgygsvlfwcwnswtuhmyaljkqlqjjqlqkjlaymhutwsnwcflvsgygh
- fgnfnidynhxebxxxfmxixhsruldhsaobhlcggchboashdlurshxixmfxxxbexhnydinfngf
- bsyhvwfuesumsehmytqioswvpcbxyolapfywdxeacyuruybhbwxjmrrmjxwbhbyuruycaexdwyfpaloyxbcpwsoiqtymhesmuseufwvhysb
- fvyqxqxynewuebtcuqdwyetyqqisappmunmnldmkttkmdlnmnumppasiqyteywdquctbeuwenyxqxqyvf
- mmbiefhflbeckaecprwfgmqlydfroxrblulpasumubqhhbvlqpixvvxipqlvbhqbumusaplulbrxorfdylqmgfwrpceakceblfhfeibmm
- tpqknkmbgasitnwqrqasvolmevkasccsakvemlosaqrqwntisagbmknkqpt
- lhrxvssvxrhl
- prcoitfiptvcxrvoalqmfpnqyhrubxspplrftomfehbbhefmotfrlppsxburhyqnpfmqlaorxcvtpiftiocrp
- kjowoemiduaaxasnqghxbxkiccikxbxhgqnsaxaaudimeowojk
我的輸出：
- 1
- 8
- 33
- 23
- 24
- 43
- 20
- -1
- 14
- -1
我在本地除錯代碼，根據我的理解，這個測驗用例運行良好。請幫我理解一下，代碼有什么問題。
注意：我可以用其他替代方法（更簡單的方法）來完成，在線提供解決方案，但我試圖了解我的一段 java 代碼有什么問題。謝謝。
uj5u.com熱心網友回復：
您的代碼在某些測驗用例上超時。嘗試洗掉每個字符然后檢查它是否是回文不是很有效。
通過首先檢查原始字串是否是回文，您可以找到它失敗的地方，這讓您只有兩種洗掉的可能性。所以你只需要嘗試這兩個。此外，您實際上不必執行洗掉操作。您可以跳過相關字符并通過跳過相應的索引繼續回文檢查。
這是一個可能的實作：
public static int palindromeIndex(String s) {
int start = 0;
int end = s.length() - 1;
while (start < end && s.charAt(start) == s.charAt(end)) {
start ;
end--;
}
if (start >= end) return -1; // already a palindrome
// We need to delete here
if (isPalindrome(s, start 1, end)) return start;
if (isPalindrome(s, start, end - 1)) return end;
return -1;
}
public static boolean isPalindrome(String s, int start, int end) {
while (start < end && s.charAt(start) == s.charAt(end)) {
start ;
end--;
}
return start >= end;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/400699.html
上一篇：不知道為什么我的C程式在處理鏈表時給出錯誤代碼“行程在2.55秒后退出，回傳值為3221225477”
下一篇：整數陣列的基于廣度級別的磁區方法