字符串字母包含算法


给定两个分别由字母组成的字符串A和字符串B,字符串B的长度比字符串A短。请问,如何最快地判断字符串B中所有字母是否都在字符串A里?为了简单起见,我们规定输入的字符串只包含大写英文字母,请实现函数
bool StringContains(string &A, string &B)


// Created by Lv,Xinwei on 2018/2/5.
/**
 * 穷举查找O(nm)
 * @param A
 * @param B
 * @return
 */
bool StringContains(string &A, string &B) {
    typedef string::const_iterator it;
    int num=0;
    for (it i = B.begin(); i < B.end(); i++) {
        for (it j = A.begin(); j < A.end(); j++) {
            if (*i == *j) {
                num++;
                break;
            }
        }
    }
    return num==B.length();
}
int  cmp(const void* a,const void*  b){
    return ( *(char*)a - *(char*)b );
}
/**
 * 排序查找O(nlogN+mlogM+m)
 * @param A
 * @param B
 * @return
 */
bool StringContains2(string &A, string &B) {
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    typedef string::const_iterator it;
    it j=A.begin();
    for (it i = B.begin(); i < B.end(); i++) {
        for (; j < A.end(); ) {
            if (*i == *j) {
                break;
            }
            j++;
        }
        if(j==A.end()){
            return false;
        }
    }
    return true;
}
/**
 * 使用map O(n+m)
 * @param A
 * @param B
 * @return
 */
bool StringContains3(string &A, string &B) {
    map<int,char> bulk;
    typedef string::const_iterator it;
    for (it i = A.begin();  i<A.end() ; i++) {
        bulk.insert(pair<char,int>(*i,1));
    }
    for (it i = B.begin();  i<B.end() ; i++) {
        if(bulk.find(*i)==bulk.end()){
            return false;
        }
    }
    return true;
}
/**
 * 使用位计算 O(n+m)
 * @param A
 * @param B
 * @return
 */
bool StringContains4(string &A, string &B) {
    int bit_counter=0;
    typedef string::const_iterator it;
    for (it i = A.begin(); i <A.end() ; i++) {
        bit_counter|=1<<((*i)-'a');
    }
    for (it i = B.begin(); i <B.end() ; i++) {
        if((bit_counter&(1<<((*i)-'a')))==0){
            return false;
        }
    }
    return true;
}
void testStringContain(){
    string s1="aafgrsdf fsefvdgdfhfg";
    string s2="absdff afsvxcvasdfc";
    cout<<StringContains(s1,s2)<<endl;
    s1="aafgrsdfsdfscde";
    s2="absdffsdafsddafqwdfc";
    cout<<StringContains2(s1,s2)<<endl;
    cout<<s1<<endl;
    map<char,int> bulk;
    typedef map<char,int>::const_iterator it;
    pair<char,int> data('s',11);
    bulk.insert(data);
    data={'s',100};
    pair<it,bool> temp=bulk.insert(data);
    cout <<temp.second<<endl;
    it iii=temp.first;
    cout <<iii->first<<iii->second<<endl;
    s1="aafsdfsdawefscde";
    s2="ab";
    cout<<StringContains3(s1,s2)<<endl;
    s1="aafgrsdefwfgjuytnwabcde";
    s2="abgfex";
    cout<<StringContains4(s1,s2)<<endl;
}
#endif //THEARTOFPROGRAMING_STRINGCONTAIN_H

发表评论

电子邮件地址不会被公开。

Time limit is exhausted. Please reload CAPTCHA.