TypeScript算法题实战——字符串篇（字符串的反转、旋转、查询、KMP算法）

原创

中杯可乐多加冰

发布于 2024-12-09 10:02:46

11600

代码可运行

运行总次数：0

代码可运行

好事发生

这里推荐一篇实用的文章：《使用Python实现智能食品消费趋势分析的深度学习模型》

作品链接：https://cloud.tencent.com/developer/article/2474802

食品行业需要紧跟市场趋势和消费者需求，以保持竞争力。通过智能化的数据分析，尤其是深度学习模型，可以帮助企业预判市场动态，制定有效的市场策略。

这篇文章详细介绍了如何使用Python构建一个智能食品消费趋势分析的深度学习模型，并通过具体代码示例展示其实现过程。系统通过分析销售数据、价格、促销等因素，预测市场趋势，实现智能化的市场分析和决策支持

下面开始今天的主题：

字符串操作是算法题中的常见考点，它们直接测试开发者对字符串类型的理解和灵活运用。字符串问题不仅基础且多样，还能延伸到动态规划、贪心算法和高级数据结构的应用。字符串的翻转、反复、旋转、替换、查询、KMP查找子串等都是很经典的题目。掌握字符串的核心操作和优化技巧，是算法学习中的必备技能。

零、常用库函数

1：join()和split() join()将数组转换成字符串，是关于数组的方法; split()将字符串切割成数组，是关于字符串的方法; split()把一个字符串(根据某个分隔符字符串)切割成若干个字符串并存放在一个数组里。而join()把数组中的字符串连成一个长串，可以认为它是split()的逆操作。如剑指 Offer 05. 替换空格:

let s:string = "abcdefg"
function replaceSpace(s: string): string {
    let arr: string[] = s.split(" ");
    return arr.join("%20");
};

一、反转字符串 II

字符串翻转是最基础的操作，通常用来测试对字符数组或字符串基本处理的熟练度。 典型问题：

将字符串从左到右翻转。例如，"hello" 翻转为 "olleh"。
翻转字符串的部分内容，比如只翻转单词，而不改变整体顺序（"I love you" → "I evol uoy"）。

1.1、题目描述

力扣链接：https://leetcode.cn/problems/reverse-string-ii/

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

1.2、示例

1.3、题解

将题目视作为多个长度为2k的子字符串，最后一位另外单独考虑，那么外循环可以设置为i = i + 2k，这样的话每次单独处理子串就好了，翻转可以设置两个指针。

function reverseStr(s: string, k: number): string {
    let tmp: string;
    let left: number;
    let right: number;
    let arr: string[] = s.split("")
    for(let i: number = 0; i < arr.length; i = i+ 2 * k){
        left = i;
        right = (i + k - 1) >= arr.length ? arr.length - 1 : i + k - 1;
        while(left < right){
            tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left ++;
            right --;
        }
    }
    return arr.join("");
};

二、反转字符串中的单词

2.1、题目描述

力扣链接：https://leetcode.cn/problems/reverse-words-in-a-string/ 给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词 顺序颠倒且 单词之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格

2.2、示例

2.3、题解

很简单的思路是：使用split函数将原字符串拆成多个子字符串，但是子字符串里肯定有一些为’'的空字符串，设定一个额外的字符串数组，遍历原字符串数组，将有内容的存入新的字符串数组，空字符串跳过。然后处理新的字符串数组，将其做反转就可以了。

function reverseWords(s: string): string {
    let arr: string[] = s.split(" ");
    let midarr: string[] = [];
    let index: number = 0;
    for(let i = 0; i < arr.length; i++){
        if(arr[i] != ''){
            midarr[index] = arr[i];
            index++;   
        }
    }
    for(let i = 0; i < midarr.length / 2; i++){
        let temp: string;
        temp = midarr[i];
        midarr[i] = midarr[length - i - 1];
        midarr[length - i - 1] = temp;
    }
    // console.log(midarr);
    return midarr.join(" ");
};

第二种方法，先删除多余的空格，再进行翻转

function reverseWords(s: string): string {
    let arr: string[] = s.split("");
    delExtraSpace(arr);
    function delExtraSpace(arr: string[]):void{
        let left: number = 0;
        let right: number = 0;
        while(arr[right] === ' ' && right < arr.length){
            right ++;
        }
        while(right < arr.length){
            if(arr[right] === ' ' && arr[right - 1] === ' '){
                right++;
                continue;
            }
            arr[left++] = arr[right++];
        }
        if(arr[left - 1] === ' ')
            arr.length = left -1;
        else
            arr.length = left;
    }

    let resarr: string[] = arr.join("").split(" ");
    for(let i:number = 0; i < resarr.length / 2; i++){
        let tmpstr: string = resarr[i]; 
        resarr[i] = resarr[resarr.length - 1 - i];
        resarr[resarr.length - 1 - i] = tmpstr;
    }
    return resarr.join(" ");
};

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

3.1、题目描述

力扣链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/ 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

3.2、示例

3.3、题解

本题要使用KMP算法，不然会严重超时，KMP（Knuth-Morris-Pratt）算法是一种高效解决子串匹配问题的经典方法，能避免暴力查找中的重复比较。KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。KMP的主要是使用空间换时间。

核心思想：

通过预处理生成部分匹配表（Partial Match Table，简称 PMT），记录模式串的最长公共前缀与后缀长度。
利用 PMT 实现快速跳跃，从而减少比较次数。

典型问题：

在字符串中查找目标子串首次出现的位置。
判断两个字符串是否循环移位后相等。

KMP算法的总时间复杂度为O(m+n)，空间复杂度记为O(m)。相比于朴素的模式匹配时间复杂度O(m*n)，KMP算法提速是非常大的，这一点点空间消耗换得极高的时间提速是非常有意义的，这种思想也是很重要的。

首先设计一个函数计算next数组（前缀表统一减一），然后进行匹配：

function strStr(haystack: string, needle: string): number {
    function getNext(str: string): number[] {
        let next: number[] = [];
        let j: number = -1;
        next[0] = j;
        for (let i = 1, length = str.length; i < length; i++) {
            while (j >= 0 && str[i] !== str[j + 1]) {
                j = next[j];
            }
            if (str[i] === str[j + 1]) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    if(needle.length === 0)
        return 0;
    let next: number[] = getNext(needle);
    // console.log(next);

    let j: number = -1;
    for(let i: number = 0; i < haystack.length; i++){
        while(j >= 0 && haystack[i] != needle[j + 1]){
            j = next[j];
        }
        if(haystack[i] === needle[j + 1]){
            if(j === needle.length - 2){
                return i - j - 1;
            }
            j++;
        }
    }
    return -1;
};

最后

🎉 支持我：点赞👍+收藏⭐️+留言📝

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S10

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S10

登录后参与评论

0 条评论

热度