提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

（字符串）子串变位词

字符串 子串
2023-09-14 08:59:06 时间

题目：

给定两个串a和b，问b是否是a的子串的变位词，例如输入a=hello，b=lel，lle，ello都是true，但b=elo是false。（字串是连续的）

思路：

  • 滑动窗口思想：动态维护一个“窗口”，比如b的长度是3，考察a[0..2],a[1..3],a[2..4]是否是b的变位词，关键在于如何与b比较？
  • hash数组统计：基于字符的特殊性，可以用[0,255]的数组来统计字符出现的次数，假设都是小写的英文字母，则用[0,25]来表示b中每个单词出现的次数，通过记录非0次出现的个数nonZero。
  • 窗口滑动，向右移动一位：

          新窗口 a[i-lenb+1…i]，旧窗口 a[i-lenb…i-1]

          扔掉a[i-lenb]，加入a[i]，具体操作参考代码，文字表达不清。

代码：

#include <iostream>
#include <vector>

using namespace std;

#define NUM 26

bool variable_bit_word(char *a,int lena,char *b,int lenb){
    vector<int> cnt(26,0);
    int nonZero=0;
    // statistic of b
    for(int i=0;i<lenb;i++){
        if(++cnt[b[i]-'a']==1) nonZero++;
    }
    // first slide window
    for(int i=0;i<lenb;i++){
        int c=a[i]-'a';
        --cnt[c];
        if(cnt[c]==0) nonZero--;
        if(cnt[c]==-1) nonZero++;
    }

    if(nonZero==0)
        return true;

    for(int i=lenb;i<lena;i++){
        int c=a[i-lenb]-'a';
        ++cnt[c];
        if(cnt[c]==1) nonZero++;
        if(cnt[c]==0) nonZero--;
        c=a[i]-'a';
        --cnt[c];
        if(cnt[c]==0) nonZero--;
        if(cnt[c]==-1) nonZero++;

        if(nonZero==0) return true;
    }

    return false;
}

int main()
{
    char a[]="hello";
    char b[]="lel";
    int lena=sizeof(a)/sizeof(a[0])-1;
    int lenb=sizeof(b)/sizeof(b[0])-1;
    cout<<variable_bit_word(a,lena,b,lenb)<<endl;
    return 0;
}

相关文章