字符串题目集合

字符串输入流

• 库 sstream
• 类 stringstream

leetcode58 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

int lengthOfLastWord(string s) {
    stringstream ss(s);
    string word;
    while (ss >> word) ;
    return word.size();
}

KMP 算法

在匹配之前需要计算匹配字符串各个位置的最长重合前后缀。初始化第一个位置为 0，后缀末尾位置从 1 开始，若当前前缀的末尾与后缀末尾相同，则更新长度；否则根据当前前缀寻找新的重合前缀，这个阶段是最难理解的部分，如下图所示。

kmp

leetcode28 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

int strStr(string haystack, string needle) {
    // next数组表示到该位置的字串的最大相同前后缀的长度
    vector<int> next(needle.size());
    int j = 0;
    next[0] = 0;
    for (int i = 1, len = needle.size(); i < len; i ++) {
        // 末尾不相同则查找以当前前缀的最大重复长度
        while (j && needle[i] != needle[j]) j = next[j - 1];
        // 末尾相同则记录长度
        if (needle[i] == needle[j]) j ++;
        next[i] = j;
    }
    // 通过回溯重合位置减少遍历次数
    for (int i = 0, j = 0, len = haystack.size(); i < len; i ++) {
        // 若当前位置不匹配则变换比对位置
        while (j && haystack[i] != needle[j]) j = next[j - 1];
        // 若比对成功则向后比对
        if (haystack[i] == needle[j]) j ++;
        // 判断是否已完成比对
        if (j == needle.size()) return i - needle.size() + 1;
    }
    return -1;
}

leetcode767 重构字符串

返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。

题解

参考题解

leetcode228 汇总区间

给定一个 无重复元素 的 有序 整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中的每个区间范围 [a,b] 应该按如下格式输出： "a->b" ，如果 a != b "a" ，如果 a == b

思路

参考leetcode 题解

• to_string 方法快速将数字转换为字符串
• 使用 i 和 j 表示区间的端点
• 在遍历的过程中，若位置 j 与位置 j+1 的值相差 1，则向右拓展区间，从而找到完整区间

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        // Lambda 函数构建字符串
        auto f = [&](int i, int j) {
            return i == j ? to_string(nums[i]) : to_string(nums[i]) + "->" + to_string(nums[j]);
        };
        // i 在迭代时为上一个区间结尾 + 1
        for (int i = 0, j, n = nums.size(); i < n; i = j + 1) {
            j = i;
            // 若差为 1，右端点移动
            while (j + 1 < n && nums[j + 1] == nums[j] + 1) {
                ++ j;
            }
            // 添加区间
            ans.emplace_back(f(i, j));
        }
        return ans;
    }
};

leetcode820 单词的压缩编码

单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足： words.length == indices.length 助记字符串 s 以 '#' 字符结尾 对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等 给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。

Trie快速判断末尾重合字串

若字符串s1完全与字符串s2的末尾部分或整体重合，则字符串s1可作为同一部分助记字符串 因此，可以使用Trie构建字符串树 为了正确计算包含关系，需要优先按照字符串长度倒序排序字符串

class Solution {
private:
    // 使用长度为26的数组存储下一个字符
    struct Node {
        vector<Node*> next;
    };
public:
    int minimumLengthEncoding(vector<string>& words) {
        int n = words.size();
        // 初始化根节点
        Node* root = new Node();
        root->next.resize(26, nullptr);
        Node* p = nullptr;
        // 按字符串长度排序
        sort(words.begin(), words.end(), [&](const string& a, const string& b) {
            return a.size() > b.size();
        });
        int count = 0;
        // 遍历各个字符串
        for (int i = 0; i < n; i ++) {
            bool include = true;
            string& w = words[i];
            p = root;
            // 从字符串尾部开始遍历
            for (int j = w.size() - 1; j >= 0; j --) {
                int charIndex = w[j] - 'a';
                // 若为非空指针则表示已有该字符序列
                if (p->next[charIndex]) {
                    p = p->next[charIndex];
                }
                // 创建新的字符
                else {
                    include = false; // 标识为新字符串
                    Node* newNode = new Node();
                    newNode->next.resize(26, nullptr);
                    p->next[charIndex] = newNode;
                    p = newNode;
                }
            }
            // 若为新字符串则加上当前字符串长度以及"#"的长度
            if (! include) count += w.size() + 1;
        }
        return count;
    }
};