在 Java 中檢查字串是否是迴文
如果從右到左的字串的字元與從左到右的字串的字元相同,則我們稱其為迴文
。ababa
、radar
和 ppqpp
等字串是一些示例。
這裡,第一個字元與最後一個字元相同;第二個字元與倒數第二個字元相同,等等。在本文中,我們將檢視各種 Java 程式來檢查字串是否為迴文。
在 Java 中使用指標檢查字串是否為迴文
檢查字串是否為迴文的一個非常簡單的想法是使用兩個指標;一個指向字串的開頭,另一個指向字串的結尾。考慮以下程式碼。
public class PalProgram{
static boolean PalFunc(String s)
{
//Pointer i pointing to the start and j pointing to the end
int i = 0, j = s.length()-1;
while(i<j){
//Check if there is any mis-matching pair
if (s.charAt(i) != s.charAt(j))
return false;
//Update the pointers
i++;
j--;
}
//If no mismatch occurs
return true;
}
public static void main(String[] args)
{
String s = "ava";
s = s.toLowerCase();
if(PalFunc(s))
System.out.print("Yes, it is a palindrome.");
else
System.out.print("No, it is not a palindrome.");
}
}
輸出:
Yes, it is a palindrome.
這裡,在 PalFunc
函式內部,第一個指標 i
將指向字串的開頭,第二個指標 j
將指向字串的結尾,我們必須檢查它是否是迴文或不。
然後,我們將執行一個迴圈,直到 i<j
。在每一步中,我們檢查這兩個指標 i
和 j
指向的字元是否匹配。
此外,我們同時將 i
遞增和 j
減一。如果字元在任何步驟都不匹配,我們返回 false
通知使用者該字串不是迴文。
我們在示例中使用了 toLowerCase()
函式。Java 編譯器根據它們的 ASCII
值比較兩個字元。
這意味著 A == a
將評估 false
。在這種情況下,字串 abA
將不會被視為 Java 中的迴文,這不是實際情況。
這就是為什麼我們必須先將字串轉換為大寫或小寫,然後才能在 for
迴圈中進行比較。在處理像 AVva
這樣的字元混合大小寫的迴文時很有幫助。
在 Java 中反轉字串以檢查字串是否為迴文
考慮我們有字串 aabcvbaa
。讓我們首先反轉字串。結果字串將是 aabvcbaa
。
原始字串的最後一個字元成為反轉字串的第一個字元。原始字串的倒數第二個字元成為反轉字串的第二個字元,依此類推。
現在,我們可以逐個字元地比較兩個字串來檢查字串是否是迴文。如果發生任何不匹配,則字串不是迴文,我們可以返回 false
,通知使用者該字串不是迴文。
但是,如果始終沒有出現不匹配,我們可以返回 true
,表示該字串是迴文。在這種情況下,我們正在建立一個新的反轉字串,而不是在同一個字串中使用兩個指標(參見演示)。
有時,我們不允許使用 Java 提供的內建函式。因此,我們不會使用 Java API 中的 reverse()
方法。
我們將編寫函式來反轉字串。
public class Solution{
static boolean Sol(String s)
{
//reverse the string
StringBuilder reversed_str = new StringBuilder();
char[] newArray = s.toCharArray();
for(int index = newArray.length - 1; index >= 0; index--){
reversed_str.append(newArray[index]);
}
//comparing the original string with the reversed string
return (reversed_str.toString()).equals(s);
}
public static void main(String[] args)
{
String s = "raceCAR";
//Convert the string to the lowercase
s = s.toLowerCase();
if(Sol(s))
System.out.print("Yes, this string is a palindrome.");
else
System.out.print("No, it isn't a palindrome.");
}
}
輸出:
Yes, this string is a palindrome.
讓我們快速看看 Sol
函式內部發生了什麼。我們首先將字串更改為陣列,然後使用它來反轉字串。
然後,我們逐個字母地將反轉的字串與原始字串進行比較。
StringBuilder
類:Java 中的字串類建立不可變字串,即不可更改的字串。在這裡,我們要建立一個字串reversed_str
,該字串是可變的以附加字元。Java 中的StringBuilder
類幫助我們建立可變字串。toCharArray
方法:由於我們要逐個字元比較原始字串和反轉字串,我們使用toCharArray()
方法將字串轉換為一系列字元。我們將結果儲存在陣列newArray
中。append()
方法:將原字串轉換為字元陣列後,用它來製作反轉後的字串。為此,我們從末尾遍歷字元陣列,並使用append()
方法繼續在字串reversed_str
中新增字元。toString()
方法:我們在製作反轉字串後使用toString()
方法再次將其更改為字串。我們這樣做是因為我們可以簡單地使用equals()
方法來比較兩個字串。
reversed_str
中附加了一個字元序列,equals()
方法比較的是字串,而不是字元序列。equals()
方法:最後,我們將原始字串s
與反轉後的字串reversed_str
進行比較。為此,我們可以使用equals()
方法,如果字串的所有字元都匹配,該方法返回true
。
如果我們使用 Java API 中的 reverse()
方法 - StringBuilder
和 StringBuffer
,我們可以輕鬆實現相同的目標,如下所示。
//Check if a string is a palindrome
//Java program
public class Solution{
static boolean Sol(String s)
{ //Using the stringbuilder API
StringBuilder newString = new StringBuilder(s);
StringBuilder rev_str = newString.reverse();
return (rev_str.toString()).equals(s);
}
public static void main(String[] args)
{
String s = "raceCAR";
//Convert the string to the lowercase
s = s.toLowerCase();
if(Sol(s))
System.out.print("Yes, it is a palindrome.");
else
System.out.print("No, it is not a palindrome.");
}
}
輸出:
Yes, it is a palindrome.
請注意,當我們使用 StringBuilder
API 時,我們不需要建立字元陣列或使用 for
迴圈反轉字串。這種方法既乾淨又簡單。
要了解有關 StringBuilder
類的更多資訊,請參閱本文件。
我們還可以使用 StringBuilder
API,如下所示。
public class CheckPalindrome{
static boolean Sol(String s)
{ //Using the stringbuffer API
StringBuffer str = new StringBuffer(s);
StringBuffer rev_str = str.reverse();
return (rev_str.toString()).equals(s);
}
public static void main(String[] args)
{
String s = "raceCAR";
//Convert the string to the lowercase
s = s.toLowerCase();
if(Sol(s))
System.out.print("Yes, it is a palindrome.");
else
System.out.print("No, it is not a palindrome.");
}
}
輸出:
Yes, it is a palindrome.
你可能想知道是什麼使 StringBuilder
和 StringBuffer
類不同,因為程式碼看起來相同。
StringBuffer
類一次只允許一個執行緒呼叫此方法。它是同步的。
另一方面,StringBuilder
方法可以由多個執行緒同時呼叫。它是非同步的。
但是,StringBuilder
類比 StringBuffer
類更有效。要了解有關 StringBuffer
類的更多資訊,請參閱本文件。
在 Java 中使用遞迴檢查字串是否為迴文
我們可以遞迴呼叫 Sol
函式來檢查字串是否為迴文。基本思想是使用遞迴來迭代字串。
public class Solution{
static boolean Sol(String s)
{
s = s.toLowerCase();
return RecursePal(s, 0, s.length()-1);
}
static boolean RecursePal(String s, int f, int b){
if(f==b){
return true;
}
if((s.charAt(f)) != (s.charAt(b))){
return false;
}
if(f < b + 1){
return RecursePal(s, f + 1, b - 1);
}
return true;
}
public static void main(String[] args)
{
String s = "raceCAR";
//Convert the string to the lowercase
s = s.toLowerCase();
if(Sol(s))
System.out.print("Yes");
else
System.out.print("No");
}
}
輸出:
Yes
在這裡,我們定義了一個函式 RecursePal
。我們傳遞字串 s
,第一個字元的索引為 f
,最後一個字元的索引為 b
作為引數。
然後,我們檢查 f
處的字元是否與 b
處的字元相同。如果是,我們返回 true
。
否則,我們返回 false
。最後,我們再次呼叫 RecursePal
函式以對整個字串重複此過程。
每次遞迴呼叫此函式時,我們都會增加 f
索引並將 b
索引減一。
まとめ
在本教程中,我們看到了 Java 中檢查字串是否為迴文串的不同方法。
我們學習瞭如何使用雙指標雙向迴圈字串。我們還看到了如何通過反轉字串並在 Java 中使用遞迴來檢查字串是否為迴文。