java经典问题：连个字符串互为回环变位

本次给大家带来的是关于判断连个字符串是否互为回环变位（Circular Rotaion）的java程序员面试经常出现的题型，给大家做了两种方式的解答，希望能帮助到你。

一般情况下都是笔试或者是直接上机操作，题型一般都是：如果字符串 s 中的字符循环移动任意位置之后能够得到另一个字符串 t，那么 s 就被称为 t 的回环变位（circular rotation）。

A string s is a circular rotation of a string t if it matches when the characters are circularly shifted by any number of positions;
e.g.,ACTGACG is a circular shift of TGACGAC,and vice versa. Detecting this condition is important in the study of genomic sequences.
Write a program that checks whether two given strings s and t are circular.

关于解答方面，我给在这里给出了2种方式：
解法一：
将s拆分成左右两部分，然后另令s'=右+左，遍历所有情况。如果是回环字符串的话，其中会有 s'=t 的情况。

public static boolean isCircularRotation(String s,String t) {
    if (s.length() != t.length())
      return false;
    int sLen = s.length();
    for (int i = 0; i <= sLen; i++) {
      // 注意subString的后角标的界限
      String sLeft = s.substring(0,i);
      String sRigth = s.substring(i + 1,sLen);
      if ((sRigth + sLeft).equals(t))
        return true;
    }
    return false;
  }

解法二：（巧妙）

public static boolean isCircularRotation_1(String s,String t) {
  return (s.length() == t.length() && (t + t).contains(s));
}

以上就是基本快速的两种解决方式，关于这个问题，再给大家看一篇很详细的判断字符串回环变位解决思路：

如果字符串s中的字符循环移动任意位置之后能够得到另一字符串t，那么s就被称为t的回环变位。例如，ACTGACG 就是 TGACGAC 的一个回环变位，反之亦然。判定这个条件在基因组序列中的研究是十分重要的。编写一个算法检查两个给定的字符串s和t是否互为回环变位。

这是我在《算法（第四版）》里看到的一道练习题 ，当时的第一想法就是遍历字符串 t，从不同的索引位置将字符串t分解成两个子串，交换顺序拼接后再与s相比是否相等。算法如下：

 public static boolean isCircularRotation(String s,String t) {
    if (s.length() != t.length()) {
      return false;
    }
    int length = s.length();
    for (int i = 1; i <= length; i++) {
      String left = s.substring(0,i);
      String right = s.substring(i,length);
      if ((right + left).equals(t)) {
        return true;
      }
    }
    return false;
  }

后来看答案，提示说可以用一行代码就能搞定了。当时想了想，感觉不太可能，就作罢了。今天重新开始学习这本书的时候，再次看到这道题，突然有了想法代码如下：

public static boolean isCircularRotation(String s,String t) {
    return s.length() == t.length() && (t + t).contains(s);
  }

解释：如果字符串s和t互为回环变位，则s可分解为“AB”，t可分解为“BA”。那么t与自身拼接后则为“BABA”，显然是会包含s的。这种思路比较巧妙，当然了，自认为算法效率并没有什么提高。

为什么大家都会对这个经典的JAVA问题困惑着？最主要的原因就是解题的思路问题：

容易想复杂的"回环变位"，思路错误，问题就会复杂化，一起来看下经典的误区和最终想明白以后的解法。

题目描述很简单:
如果字符串s重的字符循环移动任意位置之后能够得到另一个字符串t，那么s就被成为s的回环变位（circular rotation） 举例省略…
问题：请编写一个程序检查2个给定的字符串s和t是否互为回环变位。
提示:判断条件只需要一行代码

看到题目当时满脑子想的都是双重循环啊，游标移动啊各种i,j,k……
结果来一句这样的提示，当时我就受不了了，决定去看一下答案….

答案是这样的

(s.length() == t.length()) && (s.concat(s).indexOf(t) >= 0)

乍一看，好像真的可以…顿时鄙视了自己的各种游标循环i,k…
（虽然可能底层也是各种循环游标i,k,但是别人都实现了的基类直接用明显更省事…）

但是也发现自己对String类的concat函数和indexOf的各种重载不懂

一下是jdk文档的描述

public String concat(String str)将指定字符串连接到此字符串的结尾。 
如果参数字符串的长度为 0，则返回此 String 对象。否则，创建一个新的 String 对象，用来表示由此 String 对象表示的字符序列和参数字符串表示的字符序列连接而成的字符序列。

示例： 

 "cares".concat("s") returns "caress"
 "to".concat("get").concat("her") returns "together"

参数：
str - 连接到此 String 结尾的 String。 
返回：
一个字符串，它表示在此对象字符后连接字符串参数字符而成的字符。

public int indexOf(String str)返回指定子字符串在此字符串中第一次出现处的索引。返回的整数是 
 this.startsWith(str,k)
 为 true 的最小 k 值。 

参数：
str - 任意字符串。 
返回：
如果字符串参数作为一个子字符串在此对象中出现，则返回第一个这种子字符串的第一个字符的索引；如果它不作为一个子字符串出现，则返回 -1。

关于这个问题，已经在上文章阐述的非常清楚了，大家如果对此还有任何的疑问，可以在本文下方留言讨论。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!