Introduction

什麼是Palindromic String 迴文字串

所謂的Palindromic String(迴文字串) 就是以一個字元為中間，而它的左邊以及右邊的組成字元相同。
例子:
abcdcba 以d為中心的左跟右的字元一樣。
cdc左跟右都為c
bcdcb 左跟右都為b
abcdcba 左跟右都為a

要怎麼知道String是否為什麼是palindrome(迴文)

要知道String是否palindrome，我們先得知道Palindromic的規則:

• 單一的字元都是Palindromic，例如: a,b,g…
• 某字元的左右字元相同,例如: xax,xbx,xgx…
• 某字元自己跟右邊或者左邊相同也是一個也使一個palindrome。例如aa,bb
• 如果某子串為palindrome,而左跟右字元相同，它也會是一個palindrome。例如palindromeaba,它的左右2邊都為字元x,xabax也使一個palindrome; 相反，左跟右字元不相同,則只有子字串為palindrome。

判斷是否palindrome string

我可以從子串的中心點(middle point)開始往外擴展i,j,如果i跟j位置的為相同字元,則繼續往外擴。如果過程中有i,j位置的字元不相同,我們就可以知道它不是一個palindrome。

在尋找Palindrome的時候，我們必要要考慮到odd和evencase。

• odd case : 會以odd基數的方式擴展。
  • 例如: a -> bab -> cbabc…
• even case: 會以even偶數的方式擴展
  • 例如: aa -> baab -> cbaabc…

什麼時候會出現這種情況呢? 例如這個例子:baab。如果只使考慮到odd case,他會被認為不是一個Palindrome。baa,aab…都不是合法的Palindrom。所以,我們必須考慮到even case。aa,baab是合法的Palindrom。

Palindrome Template

1
2
3
4
5
6
7
8
9

    //O(n)
    bool isPalindrome(string str,int i,int j){
        while(i>=0 && j < str.length()){
            if(str[i] != str[j]) return false;
            i--;
            j++;
        }
        return true;
    }

1
2
3
4

    //中心點為Odd(i)
    isPalindrome(str,i,i);
    //中心點為even(i,i+1)
    isPalindrome(str,i,i+1);