|
LeetCode 680.驗證回文字符串Ⅱ題目鏈接: https:///problems/valid-palindrome-ii/ 題目描述: 給定一個非空字符串 s，最多刪除一個字符。判斷是否能成為回文字符串。 示例 1： 輸入: "aba" 輸出: True 示例 2： 輸入: "abca" 輸出: True 解釋: 你可以刪除c字符。 提示： 字符串只包含從 a-z 的小寫字母。字符串的最大長度是50000。 題目分析: 采用雙指針思想，首指針指向字符串開頭第一個元素，尾指針指向字符串最后一個元素，兩個指針分別向中間靠攏，檢查兩個指針指向的位置上的字符是否相同，如果相同則構成回文。在字符不同的情況下，分別檢查去掉首指針指向的字符和去掉尾指針指向的字符時是否還能構成回文，如果去掉其中一個字符能構成回文，則符合題意，返回true。否則返回false即可。 題解: 執(zhí)行用時: 10 ms 內(nèi)存消耗: 39.1 MB class Solution { public boolean validPalindrome(String s) { // 定義雙指針分別指向字符串的頭尾 int start = 0, end = s.length() - 1; // 當首指針沒有越過尾指針時執(zhí)行循環(huán) while (start < end) { // 如果首尾指針指向的位置上的字母不一致 if (s.charAt(start) != s.charAt(end)) { // 調(diào)用函數(shù)分別判斷 刪除首指針指向的元素 或者 刪除尾指針指向的元素 時是否還是一個回文字符串 return isPalindrome(s, start + 1, end) || isPalindrome(s, start, end - 1); } // 如果首尾指針指向的值一致，則檢查下一組字母 start++; end--; } // 如果構成回文字符串，則返回true return true; }
// 判斷子字符串是否構成回文字符串函數(shù) public boolean isPalindrome(String s, int start, int end) { // 當首指針沒有越過尾指針時執(zhí)行循環(huán) while (start < end) { // 如果首尾指針指向的位置上的字母不一致 if (s.charAt(start) != s.charAt(end)) { // 不構成回文字符串，返回false return false; } // 如果首尾指針指向的值一致，則檢查下一組字母 start++; end--; } // 如果構成回文字符串，則返回true return true; }}
|
