#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).
這是一個很基本的考題,如果你的面試遇到這種題目,那表示面試官根本不想為難你.




Share:

0 意見:

張貼留言