java中連個字符串是否互為回環變位

這篇文章主要為大家展示了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,j,k…
（雖然可能底層也是各種循環游標i,j,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。

以上就是關于java中連個字符串是否互為回環變位的內容，如果你們有學習到知識或者技能，可以把它分享出去讓更多的人看到。