在 Java 中檢查字串是否是迴文

Shikha Chaudhary 2023年1月30日 2022年4月22日
  1. 在 Java 中使用指標檢查字串是否為迴文
  2. 在 Java 中反轉字串以檢查字串是否為迴文
  3. 在 Java 中使用遞迴檢查字串是否為迴文
  4. まとめ
在 Java 中檢查字串是否是迴文

如果從右到左的字串的字元與從左到右的字串的字元相同,則我們稱其為迴文ababaradarppqpp 等字串是一些示例。

這裡,第一個字元與最後一個字元相同;第二個字元與倒數第二個字元相同,等等。在本文中,我們將檢視各種 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。在每一步中,我們檢查這兩個指標 ij 指向的字元是否匹配。

此外,我們同時將 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 函式內部發生了什麼。我們首先將字串更改為陣列,然後使用它來反轉字串。

然後,我們逐個字母地將反轉的字串與原始字串進行比較。

  1. StringBuilder 類:Java 中的字串類建立不可變字串,即不可更改的字串。在這裡,我們要建立一個字串 reversed_str,該字串是可變的以附加字元。Java 中的 StringBuilder 類幫助我們建立可變字串。
  2. toCharArray 方法:由於我們要逐個字元比較原始字串和反轉字串,我們使用 toCharArray() 方法將字串轉換為一系列字元。我們將結果儲存在陣列 newArray 中。
  3. append() 方法:將原字串轉換為字元陣列後,用它來製作反轉後的字串。為此,我們從末尾遍歷字元陣列,並使用 append() 方法繼續在字串 reversed_str 中新增字元。
  4. toString() 方法:我們在製作反轉字串後使用 toString() 方法再次將其更改為字串。我們這樣做是因為我們可以簡單地使用 equals() 方法來比較兩個字串。
注意
我們在 reversed_str 中附加了一個字元序列,equals() 方法比較的是字串,而不是字元序列。
  1. equals() 方法:最後,我們將原始字串 s 與反轉後的字串 reversed_str 進行比較。為此,我們可以使用 equals() 方法,如果字串的所有字元都匹配,該方法返回 true

如果我們使用 Java API 中的 reverse() 方法 - StringBuilderStringBuffer,我們可以輕鬆實現相同的目標,如下所示。

//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.

你可能想知道是什麼使 StringBuilderStringBuffer 類不同,因為程式碼看起來相同。

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 中使用遞迴來檢查字串是否為迴文。

相關文章 - Java String