跳到主要内容

11.2 字符串比较

242. Valid Anagram​

题目描述​

判断两个字符串包含的字符是否完全相同。

输入输出样例​

输入两个字符串，输出一个布尔值，表示两个字符串是否满足条件。

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

题解​

我们可以利用哈希表或者数组统计两个数组中每个数字出现的频次，若频次相同，则说明它们包含的字符完全相同。

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; });
}

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 定义下字符的总数量）。

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;
}

647. Palindromic Substrings​

题目描述​

给定一个字符，求其有多少个回文子字符串。回文的定义是左右对称。

输入输出样例​

输入是一个字符串，输出一个整数，表示回文子字符串的数量。

Input: "aaa"
Output: 6

六个回文子字符串分别是 ["a","a","a","aa","aa","aaa"]。

题解​

我们可以从字符串的每个位置开始，向左向右延长，判断存在多少以当前位置为中轴的回文子字符串。

// 辅函数。
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;
}

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 的最后一位，我们记录的相同数字长度是 1，因为只有一个连续 0；我们记录的不同数字长度是 2，因为在 0 之前有两个连续的 1。若不同数字的连续长度大于等于当前数字的连续长度，则说明存在一个且只存在一个以当前数字结尾的满足条件的子字符串。

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;
}

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) 也算正确。

题解​

因为只有一种括号，所以我们并不一定利用栈来统计，可以直接用一个临时变量统计在当前位置时，左括号比右括号多出现多少次。如果在遍历过程中出现负数，则需要移除多余的右括号。如果遍历结束时临时变量为正数，则需要从右到左移除多余的左括号。这里我们使用了一个小技巧，先标记待删除位置，最后一起移除。

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;
}