前言

在軟體工程師和程式設計的工作或面試的過程中不會總是面對到只有簡單邏輯判斷或計算的功能，此時就會需要運用到演算法和資料結構的知識。本系列文將整理程式設計的工作或面試入門常見的程式解題問題和讀者一起探討，研究可能的解決方式（主要使用的程式語言為 Python）。其中字串處理操作是程式設計日常中常見的使用情境，本文繼續將從簡單的字串處理問題開始進行介紹。

要注意的是在 Python 的字串物件 str 是 immutable 不可變的，字串中的字元是無法單獨更改變換。

舉例來說，以下的第一個指定字元變數行為是不被允許的，但整體字串重新賦值指定另外一個字串物件是可以的：

name = 'Jack'

# 錯誤
name[0] = 'L'

# 正確
name = 'Leo'

執行結果：

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

常見問題

尋找唯一字元

Problem: First Unique Character in a String
Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.

Examples:

Examples:

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

Note: You may assume the string contains only lowercase English letters.

題目意思為輸入為一個字串，回傳第一個唯一（沒有重複）的字元索引位置，若沒有的話回傳 -1。可以假定字串只包含小寫字母。

Solution

字典比對法

 class Solution:
     def firstUniqChar(self, s: str) -> int:
         # 建立一個字典儲存字元出現次數
         count_dict = {}
         # 迭代所有字串中的字元進行字元出現次數統計
         for char in s:
             # 若已有出現過的字元，統計次數增加一次
             if char in count_dict:
                 count_dict[char] += 1
             # 若沒有出現過則次數初始化為一
             else:
                 count_dict[char] = 1
         # 從頭迭代所有字串中的字元，若出現次數為一次字元回傳索引值（使用 enumerate 取出索引值和內容值）
         for index, char in enumerate(s):
             if count_dict[char] == 1:
                 return index
         return -1

字典比對法主要透過迭代所有字串中的字元進行字元出現次數統計和比對，是對於不同程式語言比較通用的寫法。

串列切片法

 class Solution:
     def firstUniqChar(self, s: str) -> int:
         # 從頭迭代所有字串中的字元和索引值，判斷在該位置之前和之後是否有相同的字元，若無代表為唯一值
         for index, char in enumerate(s):
             if char not in s[:index] and char not in s[index + 1:]:
                 return index
         return -1

串列切片法透過 Python 特殊的切片機制，讓我們可以使用簡潔的語法直接判斷是否為唯一值。

判斷易位構詞

Problem: Valid Anagram
Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:
Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

題目的意思輸入兩個字串，判斷是否為易位構詞（Anagram），易位構詞意思為一個字詞透過重新排列順序產生另外一個字詞。舉例來說 cat 和 atc 為易位構詞，因為字串長度和字母出現次數相同，只有排列順序不同。

Solution

迴圈迭代法

 class Solution:
     def isAnagram(self, s: str, t: str) -> bool:
         # 若兩個字串長度不同則不符合
         if len(s) != len(t):
             return False

         # 將兩個字串轉為串列進行排序
         list_s = list(s)
         list_s.sort()
         list_t = list(t)
         list_t.sort()

         # 透過迭代法，一一取出已排序序列進行比對
         for index, char in enumerate(list_s):
             if list_s[index] == list_t[index]:
                 continue
             else:
                 return False
         return True

主要是透過將字串轉為串列並將字元排序後一一比對。

串列移除法

 class Solution:
     def isAnagram(self, s: str, t: str) -> bool:
         if len(s) != len(t):
             return False

         # 將字串轉為串列
         list_s = list(s)
         list_t = list(t)

         # 將字串串列一一一取出
         while len(list_s) > 0:
             try:
                 # pop 出元素並確認是否有在另外一個串列中
                 char = list_s.pop(0)
                 list_t.remove(char)
             except ValueError:
                 return False
         return True

透過將字串轉為串列後將其中一個串列元素取出，並移除同樣在另外一個串列的字元，若發生無法移除錯誤代表有不同的字元組成，非易位構詞。

判斷回文字串

Problem: Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true
Example 2:

Input: "race a car"
Output: false

Constraints:

s consists only of printable ASCII characters.

題目的意思是串入一個字串，回傳判斷是否為回文（Palindrome）。回文代表的意思為從前面或從後面看來都是一樣的字串，是正讀反讀都能讀通的句子。

Solution

雙指針法：

 class Solution:
     def isPalindrome(self, s: str) -> bool:
         if len(s) < 2:
             return True
         # 將字串轉為小寫
         s = s.lower()
         # 初始化左右指針
         # 設計兩個指標分別從最左和最右出發
         pointer_left = 0
         pointer_right = len(s) - 1

         # 當左指針大於等於右指針時結束迴圈
         while pointer_right > pointer_left:
             # 左指標中，字串中有可能有非字母，透過 isalnum 進行判斷，若非字母字元則往前推進
             if not s[pointer_left].isalnum():
                 pointer_left += 1
                 continue
             # 右指標中，字串中有可能有非字母，透過 isalnum 進行判斷，若非字母字元則往前推進
             if not s[pointer_right].isalnum():
                 pointer_right -= 1
                 continue
             # 當字元比較相同則同時往前靠近
             if s[pointer_left] == s[pointer_right]:
                 pointer_left += 1
                 pointer_right -= 1
                 continue
             # 若有不符合則非回文
             else:
                 return False
         return True

透過設計兩個指標分別從最左和最右出發，可以比對是否是回文（注意要處理非字母字元狀況）。

串列切片法

 class Solution:
     def isPalindrome(self, s: str) -> bool:
         if len(s) < 2:
             return True

         filtered_str_list = []
         # 將非字母字元去除
         for char in s:
             if char.isalnum():
                filtered_str_list.append(char.lower())
         # 取中間索引
         center_index = len(filtered_str_list) // 2

         # 透過迭代取出到中間索引之前的 index
         for index in range(center_index):
             # 透過切片從頭和從尾相互比較
             if filtered_str_list[index] == filtered_str_list[len(filtered_str_list) - index - 1]:
                 continue
             # 若有不符合的狀況就是非回文
             else:
                 return False
         return True

事先透過判斷將非字母字元去除，最後透過串列切片判斷從中間切開的頭尾兩邊是否有符合回文狀況。

總結

本系列文將持續整理程式設計的工作或面試入門常見的程式解題問題和讀者一起探討，研究可能的解決方式（主要使用的程式語言為 Python）。以上介紹了幾個簡單字串操作的問題當作開頭，需要注意的是 Python 本身內建的操作方式和其他程式語言可能不同，文中所列的不一定是最好的解法，讀者可以自行嘗試在時間效率和空間效率運用上取得最好的平衡點。