11.2 字串比較

242. Valid Anagram

題目描述

判斷兩個字串包含的字元是否完全相同。

輸入輸出範例

輸入兩個字串，輸出一個布林值，表示兩個字串是否滿足條件。

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

題解

我們可以利用雜湊表或陣列來統計兩個字串中每個字元出現的頻率。如果頻率相同，則說明它們包含的字元完全相同。

C++

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    vector<int> counts(26, 0);
    for (int i = 0; i < s.length(); ++i) {
        ++counts[s[i] - ’a’];
        --counts[t[i] - ’a’];
    }
    return all_of(counts.begin(), counts.end(), [](int c) { return c == 0; });
}

Python

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    counter = Counter(s)
    counter.subtract(t)
    return all(v == 0 for v in counter.values())

複雜度分析

• 時間複雜度: $O(n)$，其中 $n$ 為字串長度
  • 計數 s 和扣減 t 都是一次線性掃描。
• 空間複雜度: $O(1)$，因為英文字母數量固定為 26 個（常數級別的額外空間）。

205. Isomorphic Strings

題目描述

判斷兩個字串是否同構。兩個字串同構的定義為，透過將一個字串中的某些相同字元轉換為另一組相同字元，能使得兩個字串相同，且不同的字元不能被轉換為相同的字元。

輸入輸出範例

輸入兩個字串，輸出一個布林值，表示兩個字串是否滿足條件。

Input: s = "paper", t = "title"
Output: true

在這個例子中，將 s 中的 p、a、e、r 轉換為 t、i、l、e，兩個字串就可以變得相同。

題解

我們可以將問題重新表述：記錄兩個字串中每個位置的字元首次出現的位置。如果兩個字串中相同位置的字元與它們的首次出現位置相同，則這兩個字串同構。

舉例來說，對於 "paper" 和 "title"，假設我們現在處理第三個字元 p 和 t，發現它們首次出現的位置都在第一個字元，這表示目前位置滿足同構條件。我們可以使用雜湊表進行儲存，或者用一個長度為 128 的陣列（ASCII 定義下的字元總數）。

C++

bool isIsomorphic(string s, string t) {
    vector<int> s_init(128, 0), t_init(128, 0);
    for (int i = 0; i < s.length(); ++i) {
        if (s_init[s[i]] != t_init[t[i]]) {
            return false;
        }
        s_init[s[i]] = t_init[t[i]] = i + 1;
    }
    return true;
}

Python

def isIsomorphic(s: str, t: str) -> bool:
    s_init, t_init = [0] * 128, [0] * 128
    
    for i in range(len(s)):
        if s_init[ord(s[i])] != t_init[ord(t[i])]:
            return False
        s_init[ord(s[i])] = t_init[ord(t[i])] = i + 1
    
    return True

複雜度分析

• 時間複雜度: $O(n)$，其中 $n$ 是字串長度，只需要一次遍歷。
• 空間複雜度: $O(1)$，因為陣列大小固定為 128（ASCII），屬於常數空間。

647. Palindromic Substrings

題目描述

給定一個字串，求其有多少個回文子字串。回文的定義是左右對稱。

輸入輸出範例

輸入是一個字串，輸出是一個整數，表示回文子字串的數量。

Input: "aaa"
Output: 6

六個回文子字串分別是 ["a", "a", "a", "aa", "aa", "aaa"]。

題解

我們可以從字串的每個位置開始，向左向右延長，判斷存在多少以當前位置為中心的回文子字串。

C++

// 輔助函式。
int extendSubstrings(string s, int l, int r) {
    int count = 0, n = s.length();
    while (l >= 0 && r < n && s[l] == s[r]) {
        --l;
        ++r;
        ++count;
    }
    return count;
}
// 主函式。
int countSubstrings(string s) {
    int count = 0;
    for (int i = 0; i < s.length(); ++i) {
        count += extendSubstrings(s, i, i);      // 奇數長度
        count += extendSubstrings(s, i, i + 1);  // 偶數長度
    }
    return count;
}

Python

# 輔助函式。
def extendSubstrings(s: str, l: int, r: int) -> int:
    count, n = 0, len(s)
    while l >= 0 and r < n and s[l] == s[r]:
        count += 1
        l -= 1
        r += 1
    return count

# 主函式。
def countSubstrings(s: str) -> int:
    return sum(
        # 奇數長度 + 偶數長度
        extendSubstrings(s, i, i) + extendSubstrings(s, i, i + 1)
        for i in range(len(s))
    )

複雜度分析

• 時間複雜度: $O(n^2)$，其中 $n$ 是字串長度。
  • 每個中心向外擴展，最壞要擴展 $O(n)$ 次。
  • 有 $2n-1$ 個中心需要檢查（奇數中心 + 偶數中心）。
• 空間複雜度: $O(1)$，只使用了常數額外空間。

696. Count Binary Substrings

題目描述

給定一個 0 和 1 組成的字串，求有多少非空子字串，其 '0' 和 '1' 的數量相同，且 '0' 和 '1' 必須連續出現（例如 "0011", "1100"；但 "0101" 不算有效）。

輸入輸出範例

輸入是一個字串，輸出是一個整數，表示符合條件的子字串的數量。

Input: "00110011"
Output: 6

在這個範例中，六個 '0' 和 '1' 數量相同的子字串為 ["0011", "01", "1100", "10", "0011", "01"]。

題解

從左往右遍歷字串，記錄當前字元連續出現的長度，以及其前一段不同字元的連續長度。例如對於字串 "00110" 的最後一位 '0'，我們記錄的值為：

• 相同字元長度為 1，因為最後只有一個連續的 '0'；
• 不同字元長度為 2，因為在最後的 '0' 之前，有兩個連續的 '1'。

若不同字元的連續長度大於等於當前字元的連續長度，則說明存在一個且僅一個以當前字元結尾、符合條件的子字串。

C++

int countBinarySubstrings(string s) {
    int prev = 0, cur = 1, count = 0;
    for (int i = 1; i < s.length(); ++i) {
        if (s[i] == s[i - 1]) {
            ++cur;
        } else {
            prev = cur;
            cur = 1;
        }
        if (prev >= cur) {
            ++count;
        }
    }
    return count;
}

Python

def countBinarySubstrings(s: str) -> int:
    prev, cur, count = 0, 1, 0
    
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            cur += 1
        else:
            prev = cur
            cur = 1
        if prev >= cur:
            count += 1
    
    return count

複雜度分析

• 時間複雜度: $O(n)$，其中 $n$ 是字串長度，只需要一次遍歷。
• 空間複雜度: $O(1)$，只用了常數空間追蹤 prev、cur、count。

1249. Minimum Remove to Make Valid Parentheses

題目描述

給定一個包含字母與括號的字串，求最少移除多少括號才能使其合法。

輸入輸出範例

輸入是一個字串，輸出是一個合法且長度最長的結果字串。

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

返回 "lee(t(co)de)" 或 "lee(t(c)ode)" 也算正確。

題解

因為只有一種括號類型，因此我們不一定需要用堆疊來統計括號對應情況。相反，我們可以使用一個臨時變數來記錄當前位置時左括號比右括號多出多少個：

• 如果在遍歷過程中，這個數值變為負數，說明有多餘的右括號需要移除。
• 若遍歷結束時這個值為正數，則說明有多餘的左括號需要移除，這可以透過從右到左的遍歷完成。

一個小技巧是先標記待刪除的位置，最後一次性移除這些位置的括號。

C++

string minRemoveToMakeValid(string s) {
    int count = 0, n = s.length();
    char to_delete = '#';
    for (char& c : s) {
        if (c == '(') { 
            ++count; 
        } else if (c == ')') {
            if (count > 0) {
                --count;
            } else {
                c = to_delete;
            }
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        if (count == 0) break;
        if (s[i] == '(') {
            s[i] = to_delete;
            --count;
        }
    }
    s.erase(remove_if(s.begin(), s.end(),
                      [to_delete](char c) { return c == to_delete; }),
            s.end());
    return s;
}

Python

def minRemoveToMakeValid(s: str) -> str:
    count, n = 0, len(s)
    to_delete = set()
    
    for i in range(n):
        if s[i] == "(":
            count += 1
        elif s[i] == ")":
            if count > 0:
                count -= 1
            else:
                to_delete.add(i)
    
    for i in range(n - 1, -1, -1):
        if count == 0:
            break
        if s[i] == "(":
            to_delete.add(i)
            count -= 1
    
    return "".join(s[i] for i in range(n) if i not in to_delete)

複雜度分析

• 時間複雜度: $O(n)$，其中 $n$ 是字串長度，因為只掃描兩遍字串。
• 空間複雜度: $O(n)$，主要是用來儲存 to_delete 集合，最壞情況下可能標記全部字元。