Eisen 筆記

#125. Valid Palindrome

題目描述

回文指的是一組片語，在把所有大寫字母轉換成小寫並且移除非字母與數字(non-alphanumeric)的字元後，由前向後、由後向前的字元排列都是一樣的。
Alphanumeric字元指的是任何的字母或數字。
給你一個字串s，如果是回文則回傳true，不是則回傳false。

限制條件

  1. 1 <= 字串s長度 <= 2*10^5
  2. s由ASCII字元所組成。

解題思路

回文的意思題目應該說明得很清楚了，就是由前向後讀會和由後向前讀一樣。 那麼剩下的工作就該如何比對字串的內容了。

字串處理 String Filter

按照步驟來的話，可以很直覺的得出先處理字串，接著檢查字串是否符合回文結構。

步驟如下：

  1. 排除不是字母、不是數字的字元。
  2. 把所有大寫字母轉換成小寫。
  3. 檢查字串內的字元是否符合回文結構。
  4. 回傳結果。
public class Solution {
	public bool IsPalindrome(string s) {
		s = StringFilter(s);
		int left=0;
		int right=s.Length-1;
		while(left<=right){
			if(left>=right) return true;
			if(s[left]!=s[right]) return false;
			left++;
			right--;
		}
        return true;
	}
	public string StringFilter(string s) {
		var t = new StringBuilder(s);
		int idx = 0;
		while(idx<t.Length){		
			if(!Char.IsLetterOrDigit(t[idx])){
				t.Remove(idx,1);
				continue;
			}
			idx++;			
		}
		for(int i=0;i<t.Length;i++){
			t[i] = Char.ToLower(t[i]);
		}
		return t.ToString();
	}
}

複雜度分析：

  • 時間複雜度：StringFilter最差的情況會花費O(2n)的時間，比對字元則會花費O(n/2)的時間，共花費(2n+n/2)的時間，因此時間複雜度為O(n)。
  • 空間複雜度：StringFilter會建立一個StringBuilder來修剪字串，使用的空間取決於s的長度，因此空間複雜度為O(n)。

雙指標 Two Pointers

在上面的解法中，我們先對字串進行處裡，之後再比對處理後的字串內容。
但事實上，我們可以直接比對字串的內容，並且略過那些不符合規則要求的字元，不需要額外去修改字串。
進行字元檢查時，我們設置了兩個指標left和right，由於回文的規則，left和right所指向的字元應該要一致。
如果不進行字串的處理，指標很可能會指到不符合規則的字元上，因此在開始字元比對之前，先將指標移動到符合規則的字元上，就可以順利比對正確的字元了。

步驟：

  1. 設置左右指標。
  2. 確認左右指標指在符合規則的字元上，反之則移動指標直到找到正確的字元或者超出限制的邊界。
  3. 兩邊都找到正確的字元後，將字元都轉換為小寫再進行比對。
  4. 重複2、3步驟，直到完成回文的檢查。
public class Solution {
	public bool IsPalindrome(string s) {		
		//
        int left=0;
        int right=s.Length-1;
        while(left<=right){
            while(!Char.IsLetterOrDigit(s[left]) && left<right) left++;
            while(!Char.IsLetterOrDigit(s[right]) && left<right) right--;
            if(left>=right) return true;
            if(Char.ToLower(s[left])!=Char.ToLower(s[right])) return false;
            left++;
            right--;
        }
        return true;
    }
}

複雜度分析：

  • 時間複雜度：最差的情況會花費掉s.Length/2的時間，因此時間複雜度為O(n)。
  • 空間複雜度：沒有使用到會增長空間的資料結構，因此空間花費為O(1)。

學習重點

  • 學習如何去操作字串。
  • 雙指標(Two Pointers)的應用。
Last Updated:
Contributors: eisen