程序员编程技术学习笔记——字符串包含

川长思鸟来 2022-08-10 11:46 159阅读 0赞

**程序员编程技术学习笔记——字符串包含**

# 1.题目描述 #

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

比如，如果是下面两个字符串：

String 1：ABCD

String 2：BAD

答案是true，即String2里的字母在String1里也都有，或者说String2是String1的真子集。

如果是下面两个字符串：

String 1：ABCD

String 2：BCE

答案是false，因为字符串String2里的E字母不在字符串String1里。

同时，如果string1：ABCD，string 2：AA，同样返回true。

# 2.解法1：暴力搜索 #

这个方法简单粗暴好想。假设两个字符串分别是str1和str2. 我们让str2中的每个字符都在str1中搜索，如果有，继续str2中的下一个字符；如果没有直接返回false。这个过程额可以用下面图示来表示：

![Center][]

假设str1.length()=n，str2.length()=m，则这种方法的时间复杂度为O(m\*n)，空间复杂度为O(1)。时间太长。

实现代码如下：

#include <iostream>
    
    using namespace std;
    
    bool StringContain(string &str1, string &str2)
    {
        int n=str1.length();
        int m=str2.length();
    
        int i, j;
        for(i=0; i<m; i++)
        {
            for(j=0; (j<n) && (str2[i]!=str1[j]); j++);  //注意判断条件
            if(j==n)
                return false;
        }
        return true;
    }
    
    int main()
    {
        string str1="ABCDE";
        string str2="CDE";
    
        bool flag;
        flag=StringContain (str1, str2);
        cout<<flag<<endl;
    
        return 0;
    }

# 3.解法2：先排序再暴力搜索 #

这种方法比上一次稍微文雅一些，文雅在没有一股脑的直接搜索，而是先把str1和str2排序，然后再那str2中的每个字符在str1中搜索。这里搜索也有讲究，不是说每次都是从头再来搜索，而是两个字符串同时前进。判断当前的str1字符和str2字符的大小，如果小，则str1的指针后移一个，继续判断。如果这个时候相等，则str2后移；否则，直接false。这点在编程中一定要注意。这种思路的时间复杂度为O(mlogm+nlogn+m+n)

我们先用下图给出该种解法的思想，然后再编程实现：

![Center 1][]

bool StringContain(string &str1,string &str2)
    {
        int n=str1.length();
        int m=str2.length();
        qsort(str1, n, sizeof(char), cmp);
        qsort(str2, m, sizeof(char), cmp);
    
        for (int p1 = 0, p2 = 0; p2 < m;)
        {
            while ((p1 < n) && (str1[p1] < str2[p2]))
            {
                ++p1;
            }
            if ((p1 >= str1.length()) || (str1[p1] > str2[p2]))
            {
                return false;
            }
            ++p2;
        }
        return true;
    }

# 4.解法3：基于HashTable #

这种方法使用的思想是基于hashtable.我们先用一个26长的数组，每个都是0.然后看str2中出现的字符就把数组中对应位置设为1.遍历一次str1,如果str1的字符在数组中为0，则不处理；如果为1，则修改为0.最后看修改的次数是否为str2的串长m，如果是，返回true；否则，为false。该解法的时间复杂度为O(m+n), 空间复杂度为O(m).

我们用下图来形象说明：

![Center 2][]

bool StringContain(string &str1, string &str2)
    {
        int n=str1.length();
        int m=str2.length();
    
        int *table=new int[m];
        memset(table, 0, m);
    
        for(int i=0; i<m; i++)
        {
            table[str2[i]-'A']=1;
        }
        int count=0;
        for(int j=0; j<n; j++)
        {
            int index=str1[j]-'A';
            if(table[index]==1)
            {
                count++;
                table[index]=0;
            }
        }
    
        if(count==m)
            return true;
        else
            return false;
    }

july的博客中用移位来写的，一样的道理。还是觉得这样写好理解一点。

# 5. 解法4：素数法 #

这种方法巧妙运用了素数的特性。假设有一个仅由字母组成字串，让每个字母与一个素数对应，从2开始，往后类推，A对应2，B对应3，C对应5，......。遍历第一个字串，把每个字母对应素数相乘。最终会得到一个整数。  
利用上面字母和素数的对应关系，对应第二个字符串中的字母，然后轮询，用每个字母对应的素数除前面得到的整数。如果结果有余数，说明结果为false。如果整个过程中没有余数，则说明第二个字符串是第一个的子集了（判断是不是真子集，可以比较两个字符串对应的素数乘积，若相等则不是真子集）。  
思路总结如下：  
  
按照从小到大的顺序，用26个素数分别与字符'A'到'Z'一一对应。  
遍历长字符串，求得每个字符对应素数的乘积。  
遍历短字符串，判断乘积能否被短字符串中的字符对应的素数整除。  
输出结果。

这种方法的时间复杂度为O(m+n)，空间复杂度为O(1)。

但是，当字符串的长度很长时，乘积就会很大，可能要涉及到大数乘除运算了。不过，个人觉得这种方法特别能够体现：好的算法都是和题目紧密结合的，这样的思想。

代码如下：

bool StringContain(string &str1, string &str2)
    {
        int n=str1.length();
        int m=str2.length();
        int prime[26]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,61, 67, 71, 73, 79, 83, 89, 97, 101};
    
        int prod=1;
        for(int i=0; i<n; i++)
        {
            int x=prime[str1[i]-'A'];
            if(prod%x)
                prod*=x;
        }
        for(int j=0; j<m; j++)
        {
            int y=prime[str2[j]-'A'];
            if(prod%y!=0)
                return false;
        }
        return true;
    }

# 6. 举一反三 #

变位词：如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，比如bad和adb即为兄弟字符串，现提供一个字符串，如何在字典中迅速找到它的兄弟字符串，请描述数据结构和查询过程。

[Center]: /images/20220810/51783aa69c524a88bd639b9c2397fa53.png
[Center 1]: /images/20220810/1b99c1d81aa642c296591758fb1fe7af.png
[Center 2]: /images/20220810/f6aeca175676479d879fa158763b5b82.png