C C++算法题解LeetCode1408数组中的字符串匹配

目录
  • 题目描述
    • 整理题意
  • 解题思路分析
    • 优化
  • 具体实现
    • 复杂度分析
  • 代码实现
    • 暴力
    • 暴力 + 优化
    • KMP
  • 总结

题目描述

题目链接:1408. 数组中的字符串匹配

给你一个字符串数组 words ,数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。

如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ,那么字符串 words[i] 就是 words[j] 的一个子字符串。

提示:

示例 1:

输入:words = ["mass","as","hero","superhero"]
输出:["as","hero"]
解释:"as" 是 "mass" 的子字符串,"hero" 是 "superhero" 的子字符串。
["hero","as"] 也是有效的答案。

示例 2:

输入:words = ["leetcode","et","code"]
输出:["et","code"]
解释:"et" 和 "code" 都是 "leetcode" 的子字符串。

示例 3:

输入: words = ["blue","green","bu"]
输出: []

整理题意

题目给定一个字符串数组 words,对于数组中的每个字符串来说,如果该字符串为数组中其他某个字符串的子串,那么就将该字符串加入答案字符串数组。可以按照任意顺序返回该答案数组。

解题思路分析

注意题目的数据提示:题目数据 保证 每个 words[i] 都是独一无二的。所以不存在两个相同的字符串,也避免了互为子字符串的情况。

根据题目数据范围来看,完全可以采用较为暴力的方法来进行解题,枚举每个字符串作为子串,检查是否为其他某个字符串的子串即可。

优化

在字符串匹配的时候可以采用 KMP 字符串匹配算法来进行优化时间复杂度。

具体实现

对于字符串匹配部分可以调用 string 中的 find() 函数进行匹配 t.find(p)(在字符串 t 中匹配字符串 p,也就是查找字符串 t 中是否包含字符串 p):

  • 此处需要用到 string 库中的 find() 函数与 string::npos 参数;

string::npos 参数是一个常数,用来表示不存在的位置。

  • stringfind() 返回值是子串的第一个字符在母串中的位置(下标记录),如果没有找到,那么会返回一个特别的标记 string::npos

可以对字符串数组 words 进行排序处理,这样就可以从最短的字符串开始匹配,且每次往后遍历匹配,因为前面的字符串一定短于当前字符串。

在使用 KMP 字符串匹配算法时需要注意:

  • KMP 字符串匹配算法的核心思想是 递归回溯思想,当匹配失败时根据 nxt 数组来进行回溯跳转;
  • nxt 数组表示模式串的子串的前缀和后缀相同的最长长度,这样就可以在匹配的过程中如果遇到不匹配的字符,模式串用 nxt 数组进行递归跳转到最长符合的位置进行继续匹配,从而不需要目标串进行重复的往返匹配。
  • 其中需要要注意的一个技巧是 nxt[0] = -1,在把 nxt 数组进行向右偏移时,第 0 位的值,我们将其设成了 -1,这只是为了编程的方便,并没有其他的意义。
  • 还需要注意 nxt 数组的优化,优化后在回溯跳转的时候会回溯跳转到首次与当前字符不一样字符的位置,避免了跳转到和当前字符一样的位置进行重复判断。
  • 在实现 getNext() 函数的时候需要注意 nxt 数组溢出问题,可以通过增加 nxt 数组大小,或减少 getNext() 函数中循环遍历的次数来防止越界出现的运行错误。
  • 需要注意在 getNext() 函数中 j 的初始化为 -1,但在 KMP() 函数中 j 的初始化为 0

复杂度分析

代码实现

暴力

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        // 新知识:string::npos
        vector<string> ans;
        ans.clear();
        // 双重循环暴力寻找
        for(auto &word1 : words){
            int l1 = word1.length();
            for(auto &word2 : words){
                int l2 = word2.length();
                // 当 l2 大于 l1 时 并且可以在 w2 中找到 w1 时
                if(l1 < l2 && word2.find(word1) != string::npos){
                    ans.emplace_back(word1);
                    break;
                }
            }
        }
        return ans;
    }
};

暴力 + 优化

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        sort(words.begin(), words.end(), [](string &a, string &b){
            return a.length() < b.length();
        });
        // 新知识:string::npos
        vector<string> ans;
        ans.clear();
        int n = words.size();
        // 双重循环暴力寻找
        for(int i = 0; i < n; i++){
            int l1 = words[i].length();
            for(int j = i + 1; j < n; j++){
                int l2 = words[j].length();
                // 当 l2 大于 l1 时 并且可以在 w2 中找到 w1 时
                if(l1 < l2 && words[j].find(words[i]) != string::npos){
                    ans.emplace_back(words[i]);
                    break;
                }
            }
        }
        return ans;
    }
};

KMP

class Solution {
    void getNext(string &p, vector<int> &nxt){
        // 把PMT进行向右偏移时,第0位的值,我们将其设成了-1,
        // 这只是为了编程的方便,并没有其他的意义。
        nxt[0] = -1;
        int i = 0, j = -1;
        int len = p.length();
        // ★注意 nxt 数组越界
        while(i < len){
            // j = -1 或者 匹配成功
            if(j == -1 || p[i] == p[j]){
                // nxt[++i] = ++j; 未优化前
                i++;
                j++;
                if(p[i] == p[j]) nxt[i] = nxt[j];
                else nxt[i] = j;
            }
            // 匹配失败,回溯
            else{
                j = nxt[j];
            }
        }
    }
    bool kmp(string &t, string &p, vector<int> &nxt){
        // ★注意这里的 j = 0 不是 j = -1
        int i = 0, j = 0;
        int lent = t.length();
        int lenp = p.length();
        while(i < lent && j < lenp){
            if(j == -1 || t[i] == p[j]){
                ++i;
                ++j;
            }
            else j = nxt[j];
        }
        if(j == lenp) return true;
        return false;
    }
public:
    vector<string> stringMatching(vector<string>& words) {
        sort(words.begin(), words.end(), [](string a, string b){
            return a.length() < b.length();
        });
        vector<string> ans;
        ans.clear();
        vector<int> nxt;
        int n = words.size();
        for(int i = 0; i < n; i++){
            int len_p = words[i].length();
            // ★注意 nxt 数组溢出
            // 可以这里 len_p + 1 也可以 getNext 中 -1
            nxt.resize(len_p + 1);
            getNext(words[i], nxt);
            for(int j = i + 1; j < n; j++){
                if(kmp(words[j], words[i], nxt)){
                    ans.emplace_back(words[i]);
                    break;
                }
            }
        }
        return ans;
    }
};

总结

  • 通过该题了解到了一个新的知识点:string::npos 参数用来表示不存在的位置。当 stringfind() 函数没有匹配成功时,那么就会返回这个参数 string::npos
  • 同时通过该题复习了 KMP 字符串匹配算法 的实现,在实现过程中需要注意 nxt 数组的大小,防止下标越界的运行错误;同时还需要注意在 getNext() 函数中 j 的初始化为 -1,但在 KMP() 函数中 j 的初始化为 0

测试结果:

以上就是C C++算法题解LeetCode1408数组中的字符串匹配的详细内容,更多关于C C++算法数组字符串匹配的资料请关注我们其它相关文章!

(0)

相关推荐

  • C++LeetCode数据结构基础详解

    目录 一.只出现一次的数字 二.多数元素 三.三数之和 总结 一.只出现一次的数字 遍历一遍数组利用异或的特性来实现(相同为0,相异为1 ) 例如[4,1,2,1,2] 4和1异或为5 5和2异或为7 7和1异或为6 6和2异或为4 这样就能找出唯一的数字了 public int singleNumber(int[] nums) { int res=0; for(int i=0;i<nums.length;i++){ res=res^nums[i]; } return res; } 二.多数元素

  • C C++ 题解LeetCode2360图中的最长环示例

    目录 题目描述 整理题意 解题思路分析 具体实现 复杂度分析 代码实现 总结 题目描述 题目链接:2360. 图中的最长环 给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,其中每个节点 至多 有一条出边. 图用一个大小为 n 下标从 0 开始的数组 edges 表示,节点 i 到节点 edges[i] 之间有一条有向边.如果节点 i 没有出边,那么 edges[i] == -1 . 请你返回图中的 最长 环,如果没有任何环,请返回 -1 . 一个环指的是起点和终点是 同一个 

  • C++实现LeetCode(347.前K个高频元素)

    [LeetCode] 347. Top K Frequent Elements 前K个高频元素 Given a non-empty array of integers, return the k most frequent elements. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] Note: You may assume

  • C C++ LeetCode题解在二叉树中增加一行示例详解

    目录 题目描述 整理题意 解题思路分析 层序遍历(广度优先搜索) 递归(深度优先搜索) 具体实现 复杂度分析 代码实现 层序遍历(广度优先搜索) 递归(深度优先搜索) 总结 题目描述 题目链接:623. 在二叉树中增加一行 给定一个二叉树的根 root 和两个整数 val 和 depth ,在给定的深度 depth 处添加一个值为 val 的节点行. 注意,根节点 root 位于深度 1 . 加法规则如下: 给定整数 depth,对于深度为 depth - 1 的每个非空树节点 cur ,创建两

  • C++实现LeetCode数组练习题

    目录 1.存在重复元素 2.最大子序和 3.两数之和 4.合并两个有序数组 5.两个数组的交集II 6.买卖股票的最佳时机 7.杨辉三角 8.重塑矩阵 9.有效的数独 10.矩阵置零 总结 1.存在重复元素 排序数组,之后遍历是否有重复的元素 public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); for(int i=1;i<nums.length;i++){ if(nums[i-1]==nums[i]){ return

  • C++ Leetcode实现从英文中重建数字

    目录 题目 分析 代码 题目 分析 首先我们先分析每个字母的组成,然后发现一些字符只在一个单词中出现,我们先去统计一下这些单词个数. z,w,u,x,g都只出现在一个数字中,也就是0,2,4,6,8,我们用哈希表统计一下s字符串中各个字符的数量,就可以知道0,2,4,6,8的数量,然后我们注意一下只在两个数字中出现的字符. h 只在 3,8 中出现.由于我们已经知道了 8 出现的次数,因此可以计算出 3 出现的次数. f 只在 4,5 中出现.由于我们已经知道了 4 出现的次数,因此可以计算出

  • C C++算法题解LeetCode1408数组中的字符串匹配

    目录 题目描述 整理题意 解题思路分析 优化 具体实现 复杂度分析 代码实现 暴力 暴力 + 优化 KMP 总结 题目描述 题目链接:1408. 数组中的字符串匹配 给你一个字符串数组 words ,数组中的每个字符串都可以看作是一个单词.请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词. 如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ,那么字符串 words[i] 就是 words[j] 的一个子字符串. 提示: 示例 1: 输入:wo

  • Java C++ 算法leetcode828统计子串中唯一字符乘法原理

    目录 题目要求 思路:模拟 java C++ Rust 题目要求 思路:模拟 解题的核心思想在于逆向思维,不考虑每个子数组中的唯一字符个数,转而考虑每个字符可以作为多少个子数组的唯一字符: 所以在计算答案时的算式和示例中给出的是不一样的: 在计算每个字符“贡献”[即当前向左向右分别可组成的答案个数]的时候要用到乘法原理. 对每一个字符s[i]s[i]s[i]都记录其左边和右边的第一个相同字符位置,分别记为l[i]l[i]l[i]和r[i]r[i]r[i],这两个位置中间构成的就是s[i]s[i]

  • 一篇文章告诉你如何在Java数组中插入一个字符

    目录 定义一个数组 定义插入的字符 打印插入之前字符排列顺序 假设插入位置 找到插入位置 数组数据下移 移入数值 输出数组 总结 定义一个数组 public class charInsert { public static void main(String[] args) { // 这是字符数组 char[] ch = new char[9]; ch[0] = 'a'; ch[1] = 'b'; ch[2] = 'c'; ch[3] = 'f'; ch[4] = 'g'; ch[5] = 'i'

  • PHP实现找出数组中出现次数超过数组长度一半的数字算法示例

    本文实例讲述了PHP实现找出数组中出现次数超过数组长度一半的数字算法.分享给大家供大家参考,具体如下: <?php * 算法要求:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字. * * 算法分析:我们需要计算数组中每个数字的出现次数.在PHP中我们可以使用in_array函数 * 来判断一个元素是否出现在数组中.比如数组中含有1,2,3三个元素,我们要判断1是否存在 * 可以使用in_array(1,$array)来判断,但是这样只能判断1出现了一次,因为对于含有数组 * 元素1

  • C++实现从数组中同时取出最大最小元素算法示例

    本文实例讲述了C++实现从数组中同时取出最大最小元素的方法.分享给大家供大家参考,具体如下: 算法思想:先相邻两个两个比较,较大的放入数组max[],较小的放入数组min[],然后从max[]数组求出最大,min[]数组求出最小即可. 比较n+[(n+1)/2] =1.5n次 #include <iostream> #define n 11 #define m ((n+1)/2) using namespace std; void main(void) { int num[] = {11,2,

  • JavaScript使用二分查找算法在数组中查找数据的方法

    本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法.分享给大家供大家参考.具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一

  • C++算法之在无序数组中选择第k小个数的实现方法

    本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法.分享给大家供大家参考,具体如下: 从一个无序的整型数组中选出第k小的数,如k=1为最小数,k=n为最大数.这里数组可以是有重复的值! 下面是自己写的一个函数,记在此处来记忆我留下的痕迹! //选择无序数组中第k小的数 #include <iostream> using namespace std ; bool failed = false ; //这里只考虑数组是int型的 int findnumber(int *array,in

  • C++二维数组中的查找算法示例

    本文实例讲述了C++二维数组中的查找算法.分享给大家供大家参考,具体如下: 一.问题: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 二.实现代码: #include <iostream> #include <vector> using namespace std; bool Find(int target, vector<vector<int>

  • Python实现在某个数组中查找一个值的算法示例

    第一种算法思路: 第一步:随机出来一个数组的下标 第二步:判断下标对应的值是否等于被查找的值,是的话终止,已找到,否的话转第三步. 第三步:判断是否随机完数组的所有下标,是的话终止,没找到,否的话转第一步. 代码如下: #本程序的功能是在字典中查找存在某个值 import random di = {'a':1,'b':2,'c':3,'d':4,'e':5,'f':6} key = 2 di1 = {} while True: tmp = random.choice(di.keys()) #随机

  • PHP实现二维数组中的查找算法小结

    本文实例讲述了PHP实现二维数组中的查找算法.分享给大家供大家参考,具体如下: 方法1:silu从左下角最后一行的第一个元素开始,遍历.如果小于target 则遍历该行的所有元素,找到结束.如果大于继续往上一行进行.等于直接结束. <?php function Find($target, $array) { $m_y = count($array['0']); $m_x = count($array); for($i=$m_x-1;$i>=0;$i--){ if($array[$i]['0']

随机推荐