(题)找兄弟子串

描述:

2016.6.21一次电话面试,面试官问了这么一个问题,感觉不难,但是当时没有想出来,好可惜。。。。

问题是:在随意一个字符串中查找abcd的变形子串。

我的方法时间复杂度为O(n),将string遍历一遍,对vector排序时间复杂度应该是O(n*logn),但是vector中始终只有4个字符,n很小,故每次排序时间复杂度可以做O(1)。另外对原始串没有任何改变。

#include "stdafx.h"
#include<iostream>
#include<string>
#include <vector>
#include<algorithm>
using namespace std;

static bool compare(const char c1,const char c2)
{
    return c1 < c2;
}

int _tmain(int argc, _TCHAR* argv[])
{
    string str;
    getline(cin,str);
    int len = str.length();
    if(len == 0)
        return 0;

    for(int i = 0;i < len; i++)
    {
        vector<char> vc;
                //将每4个字符加入vector
        for (int j = i;((i+3 <len) &&(j <=i+3)) ;j++)
            vc.push_back(str[j]);
                
                //对vector排序,记住compare函数
        sort(vc.begin(),vc.end(),compare);

        vector<char>::iterator vci = vc.begin();
        if(vc.size() == 4)
            if(*vci++ == 'a' && *vci++ == 'b' 
                           && *vci++ == 'c' && *vci =='d')
            {//如此遍历vector,我也是不知是如何想的,哈哈。实现了就好
                cout<<i<<","<<i+3<<":"<<str.substr(i,4);
                cout<<endl;
            }
    }
    system("pause");
    return 0;
}
View Code
原文地址:https://www.cnblogs.com/lp3318/p/5603142.html