C++“窗口”法寻找子串

任务

题目和解题方法来源:左神(左程云):深入解析字节跳动算法面试题与数据结构
用C++实现算法(原讲解为Java)。并通过随机新建字符串进行测试。
源代码于GitHub

题目

给定长度为m的字符串aim,以及一个长度为n的字符串str
问能否在str中找到- -个长度为m的连续子串, 使得这个子串刚好由aim的m个字符组成,顺序无所谓, 返回任意满足条件的一个子串的起始位置,未找到返回-1

思路

基本方法:遍历

找到str中所有字串substr,比较substr与aim是否成分相同(字母的种类和数量一致)

  • 统计第一个串 各字符统计
  • 遍历第二个串 — 至0 则false

窗口法

遍历所有可能的字串长度通过窗口:欠与还

解题

遍历

//比较与aim长度相同的的所有子串是否含有与它成分一致,若有,返回偏移量,否则返回-1
int findAim(string str, string aim)
{
    //cout << str.length() - aim.length() << endl;
    if (str.length() < aim.length())
        return -1;
    //数组,统计字符范围内的字符出现个数
    string substr;
    bool findAim;
    for (int i = 0; i < str.length() - aim.length(); i++)
    {
        int count[255] = {0};
        for (int i = 0; i < aim.length(); i++)
        {
            count[aim[i]]++;
        }
        substr = str.substr(i, aim.length());
        findAim = true;
        for (int i = 0; i < aim.length(); i++)
        {
            if (--count[substr[i]] < 0)
                findAim = false;
        }
        if (findAim == true)
            return i;
    }
    return -1;
}

窗口法

//比较与aim长度相同的的所有子串是否含有与它成分一致,若有,返回偏移量,否则返回-1
//法2:最优解,通过“窗口”
int findAim2(string str, string aim)
{
    //cout << str.length() - aim.length() << endl;
    if (str.length() < aim.length())
        return -1;
    //初始为aim的各字符值
    int count[255] = { 0 };
    int* pcnt = count + 97;
    for (int i = 0; i < aim.length(); i++)
        count[aim[i]]++;
    //记录窗口与aim的交易关系
    //初始值是字符总长度
    int owe = aim.length();
    //初始化第一个窗口
    for (int i = 0; i < aim.length(); i++)
    {
        //若新增的是还在需要中的,那么相当于“火中送碳”,owe--
        if (count[str[i]]-- > 0)
            owe--;
        //若新增的是之前冗余不被需要的,那么相当于“供非所求”,owe++
        else
            owe++;
    }
    if (owe == 0)
        return 0;
    //移动“窗口”,每次移动:拿去一个字符,新增一个字符,共可移动str.length() - aim.length()次
    //移除的字符是第i个,新增的字符是第i+aim.length()个
    for (int i = 0; i <= str.length() - aim.length(); i++)
    {
        //字符
        int removed = str[i], added = str[i + aim.length()];
        //判断
        //若被移除的是之前冗余不被接受的,那么相当于“及时止损”,owe--
        if (count[removed]++ < 0)
            owe--;
        //若被移除的是还在需要中的,那么相当于“屋漏偏逢连夜雨”,owe++
        else
            owe++;
        //若新增的是还在需要中的,那么相当于“火中送碳”,owe--
        if (count[added]-- > 0)
            owe--;
        //若新增的是之前冗余不被接受的,那么与最初发生的事情一致,owe++
        else
            owe++;
        //全部抵消,世界和平,移动了i次窗口,位于第i+1处
        if (owe == 0)
            return i + 1;
    }
    return -1;
}

测试

生成随机字符串

string generateArr(int len, int left, int right)
{
    if (left > right)
        return "";
    string str;// = "I lsfjo st";
    str.resize(len+1);
    for (int i = 0; i < len ; i++)
    {
        str[i] = left + rand() % (right - left);
        //cout<<str[i] << endl;
    }
    return str;
}

Leave a comment

Your email address will not be published. Required fields are marked *