【算法】字符串循环移位后是否包含

偏执的太偏执、 2022-06-02 02:43 185阅读 0赞

### 问题 ###

> 给定两个字符串s1和s2，要求判断s2是否能够被通过s1做循环移位（rotate）得到的字符串包含。  
> 例如，s1=AABCD和s2=CDAA，返回true；给定s1=ABCD和s2=ACBD，返回false。

### 解法一 ###

最直接最笨的方法就对s1进行循环移动，再进行字符串包含的判断，从而遍历其所有的可能性。字符串循环移动，时间复杂度为O（n），字符串包含判断，采用普通的方法，时间复杂度为O（n\*m），总体复杂度为O（n\*n\*m）。字符串包含判断，若采用KMP算法，时间复杂度为O（n），这样总体的复杂度为O（n\*n）。若字符串的长度n较大，显然效率比较低。其中n为s1的长度，m为s2的长度。

### 解法二 ###

对s1的循环移位操作，可以使用拼接s1+s1的方式得到。

以S1 = ABCD为例，先分析对S1进行循环移位之后的结果，如下所示：

> ABCD—>BCDA—->CDAB—->DABC—->ABCD……

假设我们把前面的移走的数据进行保留，会发现有如下的规律：

> ABCD—>ABCDA—->ABCDAB—->ABCDABC—->ABCDABCD……

因此，可以看出对s1做循环移位所得到的字符串都将是字符串s1s1的子字符串。如果s2可以由s1循环移位得到，那么s2一定在s1s1上，这样时间复杂度就降低了。

/**
     * 解法二，拼接字符串s1+s1
     * 如果s2可以由s1循环移位得到，那么s2一定在s1s1上
     */
    public static boolean isContainsByConcat(String a, String b){
        if(a == null || b == null || a.isEmpty() || b.isEmpty()) return false;
    
        String newStr = a.concat(a);
        return newStr.contains(b);
    }

### 解法三 ###

使用指针循环。我们的想法是，在s1后面”虚拟”地接上一个s1，这个”虚拟的s1”并不占空间，但是仍然按照解法2的思路进行。那么，如何实现这个”虚拟的s1”呢？其实只要把s1的最后一个元素，再指回s1的第一个元素即可。这可以用取模运算实现。比如，元素s1\[(d1+i) mod d1\]其实就是那个“虚拟的s1”的第i个元素，不会超出字符串s1的长度。

用一个指针标记遍历s1，最多两遍，与s2中的第一个字符比对，如果命中则进入s2，进行逐位匹配，匹配失败的话跳出s2继续查找s1。

/**
     * 解法三：指针循环查找
     */
    public static boolean isContainsByPointer(String a, String b){
        if(a == null || b == null || a.isEmpty() || b.isEmpty()) return false;
    
        int p = 0;  //s1的指针
    
        int aLen = a.length();
        int bLen = b.length();
        for(int i = 0; i < aLen * 2; i++){
            char c1 = a.charAt(p % aLen);
    
            //匹配到第一个字符相同后，遍历s2字符串
            if(c1 == b.charAt(0)){
                for(int j = 0; j < bLen; j++){
                    if(a.charAt((p + j) % aLen) != b.charAt(j)){
                        break;  //本次不完全匹配，继续往后
                    }
                }
                return true;
            }
            p++;
        }
        return false;
    }

优点：

1.  字符串长度较大时，效率依然较好；
2.  不需要申请额外空间存储第二个s1

### 参考资料 ###

*  [字符串移位包含的问题][Link 1]

[Link 1]: http://www.cnblogs.com/sooner/p/3270548.html

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关字符串移位包含问题

include <stdio.h> include <stdlib.h> include <string.h> int main(int arg

小灰灰/ 2022年12月11日 13:50/ 0 赞/ 106 阅读

相关字符串是否包含问题

题目描述假设这有两个分别由字母组成的字符串A另外字符串B，字符串B的字母数较字符串A少一些。什么方法能最快地查出字符串B所有字母是不是都在字符串A里？也就是说判断字符串

柔光的暖阳◎/ 2022年08月27日 05:50/ 0 赞/ 235 阅读

相关字符串移位包含的问题——解题笔记

字符串移位包含的问题——解题笔记题目描述：给定两个字符串s1和s2，要求判定s2时候能够被s1做循环移位（rotate）得到的字符串包含。例如，给定s1=AAB

墨蓝/ 2022年08月06日 17:10/ 0 赞/ 145 阅读

相关编程之美-字符串移位包含的问题

第三章　3.1　字符串移位包含的问题问题详细描述: 给定两个字符串s1和s2，要求判断s2是否能够被s1做循环移位得到的字符串包含。输入输出示例：给定s1

ゝ一世哀愁。/ 2022年08月04日 12:48/ 0 赞/ 158 阅读

相关字符串移位包含的问题

问题：给定两个字符串s1和s2，要求判断s2是否能够被通过s1做循环移位（rotate）得到的字符串包含。例如，S1=AABCD和s2=CDAA，返回true；给定s1=ABC

清疚/ 2022年07月18日 01:12/ 0 赞/ 129 阅读

相关 Java循环判断数组中是否包含字符串

关于Java循环判断数组中是否包含字符串的方法： // 循环判断数组中是否包含字符串 public static boolean useLoop(Strin

古城微笑少年丶/ 2022年07月14日 23:29/ 0 赞/ 251 阅读

相关【算法】字符串循环移位后是否包含

问题 > 给定两个字符串s1和s2，要求判断s2是否能够被通过s1做循环移位（rotate）得到的字符串包含。 > 例如，s1=AABCD和s2=CDAA，返回tru

偏执的太偏执、/ 2022年06月02日 02:43/ 0 赞/ 186 阅读

相关字符串移位包含问题研究

问题：给定两个字符串s1和s2，要求判定s2是否能够通过s1做循环移位得到字符串包含，例如s1=AABCD，s2=CDAA，则返回true，如果s1=ABCD，s2=ACBD，

痛定思痛。/ 2022年05月15日 01:35/ 0 赞/ 180 阅读

相关检测字符串是否包含中文

import org.apache.commons.lang3.StringUtils; import java.util.regex.Mat

Myth丶恋晨/ 2022年05月14日 02:18/ 0 赞/ 308 阅读

相关【编程之美】字符串移位包含的问题

问题描述：给定两个字符串s1和s2，要求判定s2是否能被s1循环移位（rotate）得到的字符串包含。例如，给定字符串s1=AABCD和s2=CDAA，返回true；给定s

妖狐艹你老母/ 2022年04月24日 15:28/ 0 赞/ 185 阅读