C ++程序中所有单词串联的子字符串

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个字符串s，并且还有一个单词列表，数组中存在的单词长度都相同。我们必须找到s中所有子字符串的起始索引，该索引是每个单词在单词中的连接，且一次没有任何中间字符。

因此，如果输入像“ barfoothefoobarman”，而单词是[“ foo”，“ bar”]，那么输出将是[0,9]。这是因为从索引0和9开始的子字符串是“ barfoo”和“ foobar”。

为了解决这个问题，我们将遵循以下步骤-

  • 定义一个名为的方法ok()，它将采用字符串s，映射wordCnt和n-

  • 将s复制到临时文件

  • 对于范围在n到s的i – 1

    • 如果在wordCnt中不存在temp时，则返回false

    • 除此以外

    • 如果wordCnt [temp]为1，则从wordCnt删除temp，将temp设置为空字符串

    • 否则，将wordCnt [temp]的值减小1，将temp设置为空字符串。

    • 如果temp的大小是0的倍数，则

    • 将温度提高s [i]

    • 如果temp不在wordCnt中，则返回false

    • 除此以外

      • 如果wordCnt [temp]为1，则从wordCnt删除temp，将temp设置为空字符串

      • 否则，将wordCnt [temp]的值减小1，将temp设置为空字符串。

    • 当wordCnt的大小为0时返回true

    • 从主要方法中，执行此操作

    • 如果a的大小为0，或b的大小为0，则返回空数组

    • 制作一个映射wordCnt，将b中存在的字符串的频率存储到wordCnt中

    • 制作一个称为ans的数组

    • 窗口：=单词数x每个单词中的字符数

    • 将字符串a的一个副本复制到temp

    • 对于范围窗口中的我，其大小为– 1

      • 将i –窗口插入ans

      • 如果临时大小可以被窗口整除并调用ok（temp，wordCnt，b [0]的大小），则

      • 在温度中插入a [i]

      • 如果temp的大小> window，则从0，1删除子字符串

    • 如果临时大小可以被窗口整除并调用ok（temp，wordCnt，b [0]的大小），则

      • 在窗口中插入一个–窗口的大小

    • 返回ans

    例 

    让我们看下面的实现以更好地理解-

    #include <bits/stdc++.h>
    using namespace std;
    void print_vector(vector<auto> v){
       cout << "[";
       for(int i = 0; i<v.size(); i++){
          cout << v[i] << ", ";
       }
       cout << "]"<<endl;
    }
    class Solution {
    public:
       bool ok(string s, unordered_map <string, int> wordCnt, int n){
          string temp = "";
          for(int i = 0; i < n; i++){
             temp += s[i];
          }
          for(int i = n; i < s.size(); i++){
             if(temp.size() % n == 0){
                if(wordCnt.find(temp) == wordCnt.end())return false;
             else{
                if(wordCnt[temp] == 1){
                   wordCnt.erase(temp);
                   temp = "";
                }
                else{
                   wordCnt[temp]--;
                   temp = "";
                }
             }
          }
          temp += s[i];
       }
       if(wordCnt.find(temp) == wordCnt.end())return false;
       else{
          if(wordCnt[temp] == 1){
             wordCnt.erase(temp);
             temp = "";
          }
          else{
             wordCnt[temp]--;
             temp = "";
          }
       }
       return wordCnt.size() == 0;
    }
    vector<int> findSubstring(string a, vector<string> &b) {
       if(a.size() == 0 || b.size() == 0)return {};
          unordered_map <string, int> wordCnt;
       for(int i = 0; i < b.size(); i++)wordCnt[b[i]]++;
          vector <int> ans;
       int window = b.size() * b[0].size();
       string temp ="";
       for(int i = 0; i < window; i++)temp += a[i];
       for(int i = window; i < a.size(); i++){
          if(temp.size() % window == 0 && ok(temp, wordCnt, b[0].size())){
             ans.push_back(i - window);
          }
          temp += a[i];
          if(temp.size() > window)temp.erase(0, 1);
       }
       if(temp .size() % window ==0 && ok(temp, wordCnt, b[0].size()))ans.push_back(a.size() - window);
          return ans;
       }
    };
    main(){
       vector<string> v = {"foo", "bar"};
       Solution ob;
       print_vector(ob.findSubstring("barfoothefoobarman", v));
    }

    输入值

    1,2,3,4,5,6,7
    3

    输出结果

    [0, 9, ]

    以上是 C ++程序中所有单词串联的子字符串 的全部内容， 来源链接： utcz.com/z/321689.html

    回到顶部