首页 » 编程之美 » 正文

[leetcode_30]Substring with Concatenation of All Words

暴力bf过的。
使用map来查找当前定长的字符串是否是“需要”[需要找到]的。

class Solution {
public:
    bool *flag;
    int len;
    vector<int>result;
    vector<int>copy;
    int sum;
    vector<int> findSubstring(string S, vector<string> &L) {
        result.clear();
        if(L.size() <= 0)return result;
        map<string,int>mapr;
        mapr.clear();
        vector<vector<int>>rtable;
        rtable.clear();
        len = L[0].size();
        map<string,int>::iterator it;
        for(int i = 0;i < L.size();i++) {
            it = mapr.find(L[i]);
            if(it != mapr.end()) {
                it->second += 1;
            }
            else
                mapr.insert(map<string,bool>::value_type(L[i],1));
        }
        copy.clear();
        sum = 0;
        for(it = mapr.begin();it != mapr.end();it++) {
            copy.push_back(it->second);
            sum += it->second;
        }
        bfs(mapr,S,0);
        return result;
    }
private:
    void bfs(map<string,int>&mapr,string &S,int start) {
        if(S.length() - start < sum * len)return ;
        int position;
        map<string,int>::iterator it;
        int min = S.length();
        for(it = mapr.begin();it != mapr.end();it++) {
            string item = it->first;
            if((position = S.find(item,start)) == string::npos)return ;
            if(position < min)
                min = position;
        }
        int i = 0;
        int end;
        if(bfsStep(mapr,min,S,end)) {
            end = min + 1;
            result.push_back(min);
        }
        end = min + 1;
        if(end >= S.length())return;
        return bfs(mapr,S,end);
    }
    void resetMapr(map<string,int>&mapr) {
        int i = 0;
        map<string,int>::iterator it;
        for(it = mapr.begin();it != mapr.end();it++) {
            it->second = copy[i++];
        }
    }
    bool bfsStep(map<string,int>&mapr,int pos,string &S,int &end) {
        int count = 0;
        map<string,int>::iterator it;
        int i;
        for(i = pos;i < S.length();i+=len) {
            it = mapr.find(string(S,i,len));
            if(it == mapr.end() || it->second <= 0) {
                end = i+len;
                resetMapr(mapr);
                return false;
            }
            it->second--;
            count++;
            if(count == sum) {
                resetMapr(mapr);
                return true;
            }
        }
        resetMapr(mapr);
        if(count == sum)return true;
        end = i;
        return false;
    }
};

发表评论