#30 Coding面試 - LeetCode #125 Valid Palindrome

題目的網址: https://leetcode.com/problems/valid-palindrome/

這一種題目算是蠻基本的，以前在台灣找工作時曾遇過有個公司的考卷出這一題，而在美國找工作時，目前還沒遇過有人考這一題或是相似的題目．

基本上，這題就是要寫一個 function 來驗證輸入的字串參數是不是 palindrome．所謂的 palindrome 就是字串中第一個位置和最後一個位置的值是一樣，第二個位置和倒數第二個位置的值是一樣，以此類推．所以一個很簡單的想法就是只要一個 for loop 就可以做完這樣的工作，而且不需要線性成長的空間，因此時間上是 O(n)，空間上是O(1)，這是對答案的要求了．

但 LeetCode 出的這一題有一點點小小的變化，因為輸入字串中可能會有其他的符號，而這些符號是不列入規則的，所以題目上寫 "A man, a plan, a canal: Panama" 是一個合格的 palindrome，因為只要不是符號類的字元都一律跳過．因為有這樣的小變化，我們除了用一個變數來記錄前面開始的比較位置，也還多用了一個變數來記錄從後面過來的比較位置．由於這是固定的兩個變數，數量不會隨著輸入參數而改變，所以在記憶體空間使用上是固定的．

另外，我們透過一個基本的 function (IsLetterOrDigit) 來幫助我們辦別輸入字元是字母還是數字，我們假設 IsLetterOrDigit 的時間複雜度是 O(1)．實際上 O(1) 是可以做的到．最後，整個程式如下:

這個程式碼的時間複雜度是 O(n) , 而空間複雜度是 O(1).
這是一個很基本的考題，如果你的面試遇到這種題目，那表示面試官根本不想為難你．