【問題描述】[簡單]

給定一個字符串，驗證它是否是回文串，只考慮字母和數(shù)字字符，可以忽略字母的大小寫。說明：本題中，我們將空字符串定義為有效的回文串。示例 1:輸入: "A man, a plan, a canal: Panama" 輸出: true 示例 2:輸入: "race a car" 輸出: false

【解答思路】

1. 篩選 + 判斷

時間復(fù)雜度：O(N) 空間復(fù)雜度：O(N)

public boolean isPalindrome(String s) {StringBuffer sgood = new StringBuffer();int length = s.length();for (int i = 0; i < length; i++) {char ch = s.charAt(i);if (Character.isLetterOrDigit(ch)) {sgood.append(Character.toLowerCase(ch));}}StringBuffer sgood_rev = new StringBuffer(sgood).reverse();return sgood.toString().equals(sgood_rev.toString());}

class Solution {public boolean isPalindrome(String s) {StringBuffer sgood = new StringBuffer();int length = s.length();for (int i = 0; i < length; i++) {char ch = s.charAt(i);if (Character.isLetterOrDigit(ch)) {sgood.append(Character.toLowerCase(ch));}}int n = sgood.length();int left = 0, right = n - 1;while (left < right) {if (Character.toLowerCase(sgood.charAt(left)) != Character.toLowerCase(sgood.charAt(right))) {return false;}++left;--right;}return true;} }

2.原字符串判斷

時間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

class Solution {public boolean isPalindrome(String s) {int n = s.length();int left = 0, right = n - 1;while (left < right) {while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {++left;}while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {--right;}if (left < right) {if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {return false;}++left;--right;}}return true;} }

3. 手寫庫函數(shù)

時間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

class Solution {public boolean isPalindrome(String s) {int start = 0;int end = s.length() - 1;while (start < end) {while (start < end && !isLetterOrDigit(s.charAt(start))) start++;while (start < end && !isLetterOrDigit(s.charAt(end))) end--;if (toLowerCase(s.charAt(start)) != toLowerCase(s.charAt(end))) return false;start++;end--;}return true;}public boolean isLetterOrDigit(Character c) {if (('0' <= c && c <= '9') || ('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z')) {return true;}return false;}public Character toLowerCase(Character c) {if ('A' <= c && c <= 'Z') {return (char)(c + 32);}return c;} }

【總結(jié)】

1.思路 單獨拉出來 或者 原字符串上操作

2.Java String類

1 char charAt(int index)
返回指定索引處的 char 值。
2 int compareTo(Object o)
把這個字符串和另一個對象比較。
3 int compareTo(String anotherString)
按字典順序比較兩個字符串。
4 int compareToIgnoreCase(String str)
按字典順序比較兩個字符串，不考慮大小寫。
5 String concat(String str)
將指定字符串連接到此字符串的結(jié)尾。
6 boolean contentEquals(StringBuffer sb)
當(dāng)且僅當(dāng)字符串與指定的StringButter有相同順序的字符時候返回真。
7 static String copyValueOf(char[] data)
返回指定數(shù)組中表示該字符序列的 String。
8 static String copyValueOf(char[] data, int offset, int count)
返回指定數(shù)組中表示該字符序列的 String。
9 boolean endsWith(String suffix)
測試此字符串是否以指定的后綴結(jié)束。
10 boolean equals(Object anObject)
將此字符串與指定的對象比較。
11 boolean equalsIgnoreCase(String anotherString)
將此 String 與另一個 String 比較，不考慮大小寫。
12 byte[] getBytes()
使用平臺的默認(rèn)字符集將此 String 編碼為 byte 序列，并將結(jié)果存儲到一個新的 byte 數(shù)組中。
13 byte[] getBytes(String charsetName)
使用指定的字符集將此 String 編碼為 byte 序列，并將結(jié)果存儲到一個新的 byte 數(shù)組中。
14 void getChars(int srcBegin, int srcEnd, char[] dst, int dstBegin)
將字符從此字符串復(fù)制到目標(biāo)字符數(shù)組。
15 int hashCode()
返回此字符串的哈希碼。
16 int indexOf(int ch)
返回指定字符在此字符串中第一次出現(xiàn)處的索引。
17 int indexOf(int ch, int fromIndex)
返回在此字符串中第一次出現(xiàn)指定字符處的索引，從指定的索引開始搜索。
18 int indexOf(String str)
返回指定子字符串在此字符串中第一次出現(xiàn)處的索引。
19 int indexOf(String str, int fromIndex)
返回指定子字符串在此字符串中第一次出現(xiàn)處的索引，從指定的索引開始。
20 String intern()
返回字符串對象的規(guī)范化表示形式。
21 int lastIndexOf(int ch)
返回指定字符在此字符串中最后一次出現(xiàn)處的索引。
22 int lastIndexOf(int ch, int fromIndex)
返回指定字符在此字符串中最后一次出現(xiàn)處的索引，從指定的索引處開始進(jìn)行反向搜索。
23 int lastIndexOf(String str)
返回指定子字符串在此字符串中最右邊出現(xiàn)處的索引。
24 int lastIndexOf(String str, int fromIndex)
返回指定子字符串在此字符串中最后一次出現(xiàn)處的索引，從指定的索引開始反向搜索。
25 int length()
返回此字符串的長度。
26 boolean matches(String regex)
告知此字符串是否匹配給定的正則表達(dá)式。
27 boolean regionMatches(boolean ignoreCase, int toffset, String other, int ooffset, int len)
測試兩個字符串區(qū)域是否相等。
28 boolean regionMatches(int toffset, String other, int ooffset, int len)
測試兩個字符串區(qū)域是否相等。
29 String replace(char oldChar, char newChar)
返回一個新的字符串，它是通過用 newChar 替換此字符串中出現(xiàn)的所有 oldChar 得到的。
30 String replaceAll(String regex, String replacement
使用給定的 replacement 替換此字符串所有匹配給定的正則表達(dá)式的子字符串。
31 String replaceFirst(String regex, String replacement)
使用給定的 replacement 替換此字符串匹配給定的正則表達(dá)式的第一個子字符串。
32 String[] split(String regex)
根據(jù)給定正則表達(dá)式的匹配拆分此字符串。
33 String[] split(String regex, int limit)
根據(jù)匹配給定的正則表達(dá)式來拆分此字符串。
34 boolean startsWith(String prefix)
測試此字符串是否以指定的前綴開始。
35 boolean startsWith(String prefix, int toffset)
測試此字符串從指定索引開始的子字符串是否以指定前綴開始。
36 CharSequence subSequence(int beginIndex, int endIndex)
返回一個新的字符序列，它是此序列的一個子序列。
37 String substring(int beginIndex)
返回一個新的字符串，它是此字符串的一個子字符串。
38 String substring(int beginIndex, int endIndex)
返回一個新字符串，它是此字符串的一個子字符串。
39 char[] toCharArray()
將此字符串轉(zhuǎn)換為一個新的字符數(shù)組。
40 String toLowerCase()
使用默認(rèn)語言環(huán)境的規(guī)則將此 String 中的所有字符都轉(zhuǎn)換為小寫。
41 String toLowerCase(Locale locale)
使用給定 Locale 的規(guī)則將此 String 中的所有字符都轉(zhuǎn)換為小寫。
42 String toString()
返回此對象本身（它已經(jīng)是一個字符串！）。
43 String toUpperCase()
使用默認(rèn)語言環(huán)境的規(guī)則將此 String 中的所有字符都轉(zhuǎn)換為大寫。
44 String toUpperCase(Locale locale)
使用給定 Locale 的規(guī)則將此 String 中的所有字符都轉(zhuǎn)換為大寫。
45 String trim()
返回字符串的副本，忽略前導(dǎo)空白和尾部空白。
46 static String valueOf(primitive data type x)
返回給定data type類型x參數(shù)的字符串表示形式。

3. 邊界條件要處理好 防止下標(biāo)越界

轉(zhuǎn)載：https://leetcode-cn.com/problems/valid-palindrome/solution/yan-zheng-hui-wen-chuan-by-leetcode-solution/

總結(jié)

以上是生活随笔為你收集整理的[Leedcode][JAVA][第125题][验证回文串][双指针][String]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。