在C ++中查找字符串中的所有字母

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

假设我们有一个字符串s和一个非空字符串p，我们必须在s中找到p的字谜的所有起始索引。这些字符串仅包含小写字母，并且字符串s和p的长度都不会大于20和100。因此，例如，如果s：“ cbaebabacd” p：“ abc”，则输出将为[0，6 ]，在索引0处为“ cba”，另一个为“ bac”，它们是“ abc”的字谜。

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

  • 定义一个映射m，n：= s的大小，设置左：= 0，右：= 0，计数器：= p的大小

  • 定义一个数组

  • 将p中的字符频率存储到映射m中

  • 正确：= 0至n – 1

    • 而左<右，

    • 如果m没有s [left]，则设置left：= right + 1

    • 如果m中不存在s [left]，则将counter增加1，并将m [s [left]]增加1

    • 向左增加1

    • 如果m具有s [right]且m [s [right]]非零，则将right减1，然后从循环中得出

    • 如果m具有s [right]且m [s [right]]非零，则将m [s [right]]减1，将counter减1，如果counter = 0，则将left插入ans

    • 除此以外

    • 返回ans

    例子（C ++）

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

    #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:
       vector<int> findAnagrams(string s, string p) {
          map <char, int> m;
          int n = s.size();
          int left = 0, right = 0;
          int counter = p.size();
          vector <int> ans;
          for(int i = 0; i < p.size(); i++) m[p[i]]++;
          for(int right = 0; right < n; right++){
             if(m.find(s[right]) != m.end() && m[s[right]]){
                m[s[right]]--;
                counter--;
                if(counter == 0)ans.push_back(left);
             } else {
                while(left<right){
                   if(m.find(s[left]) != m.end()) {
                      counter++;
                      m[s[left]]++;
                   }
                   left++;
                   if(m.find(s[right]) != m.end() && m[s[right]]){
                      right--;
                      break;
                   }
                }
                if(m.find(s[left])==m.end())left = right + 1;
             }
          }
          return ans;
       }
    };
    main(){
       Solution ob;
       print_vector(ob.findAnagrams("cbaebabacd", "abc")) ;
    }

    输入项

    "cbaebabacd"
    "abc"

    输出结果

    [0, 6, ]

    以上是 在C ++中查找字符串中的所有字母 的全部内容， 来源链接： utcz.com/z/357530.html

    回到顶部