题目：

给定一个字符串及一个字符串集合A，求该字符串中包含A中所有字符的最短子串长度。

 

解决方案一：

最直接的方法就是，直接开始遍历：查找任意两个子串之间是否包含str2，如果包含，记录下长度，求得最小值即可。

str1 = "daebfacba";

str2 = "abc";

minLen = len(str1);

for i = 0:len(str1)

    for j = i+1:len(str1)

        if (isContainAllElements(str1,str2,i,j)) //如果i到j的子串包含所有字符，则记录长度

            if j-i < minLen

                minLen = j-i;

考虑isContainAllElements()，复杂度为O(n3)。

 

解决方案二：

为str2中的每一个字符设置一个变量，用来存储最新的在str1中出现的位置。用H(x)来表示该数值。

以“daebfacba”为例，

1. 扫描到第一个a时，H(a)=1; H(b),H(c)无值；

2. 扫描到第一个b时，H(a)=1; H(b)= 3,H(c)无值；

3.扫描到第二个a时，由于C还无值，因此，直接覆盖a的值：H(a)=5; H(b)=3,H(c)无值；

4. 扫描到第一个c时，H(a)=5; H(b)=3,H(c)=6，此时计算一次距离，即用最大值减去最小值为3；

5.继续扫描，到第二个b时，H(a)=5; H(b)=7,H(c)=6，此时距离为7-5=2；

6.继续扫描，到第三个a时，H(a)=8; H(b)=7,H(c)=6，此时距离为8-6=2；

则最小值为2.

 

该算法复杂度O(n)。

该算法中，在所有字符对应位置未全找到时可以直接覆盖，能否覆盖的简单可行性论证如下：

假设a出现两次，b和c有三种相对位置可以出现：

（1）a ... b ... a ... c...

此时，第二个a会覆盖第一个a，但由于c在第二个a后面，因此仅需要计算第二个a就可以了，覆盖是可以的。

（2）a ... b...c ... a ...

此时，两个a都会参与计算，不存在覆盖问题。

（3）a...a...b..c...

此时，显然可见，只需要计算第二个a，覆盖是可以的。

因此，总结一下，覆盖的方法是可行的。

总体思路为：

1. 扫描字符串，如果遇到集合中的字符，则将集合中字符所在位置记录下来

2. 如果所有字符的位置还有未找到的，直接填充或者覆盖；

此时，如果都找到了，则计算距离，并于最短距离进行比较；否则，按照上述规则继续填充；

3. 扫描完字符串即可得到最短子串长度，同时还可以记录下所有字符的位置。

 

解决方案三：

见《编程之美》231页。

主要思想是：采用两个指针

（1）如果两指针之间不完全包含所有元素，后面的指针后移；

（2）如果包含了所有元素，则更新最短子串长度，并记录最短子串起止位置；同时，前面的指针后移。

仔细研究会发现，解决方案三跟方案二其实是一样的思想。

均需要不断监测是否填满，或包含全部元素。

拓展：

题目：

给定一个字符串及一个字符串集合A，求该字符串中包含A中所有字符的最长子串长度（不允许A中的字符在子串中重复）。

例如，“ababcda”，“abc”

思路类似，规则如下：

1. 如果各字符对一个的值未填满时：

（1）当前字符对应值未填，则直接填入；

（2）当前字符对应值已经填充（例如，H(a)=2），则清除a位置2及2之前的已经填充的值，并且重新填入a的值（例如H(a)=4）；（因为出现了重复，需要清空前面的）

 

鸣谢：

版权声明：本文为博主原创文章，未经博主允许不得转载。