本次給大家?guī)?lái)的是關(guān)于判斷連個(gè)字符串是否互為回環(huán)變位（Circular Rotaion）的java程序員面試經(jīng)常出現(xiàn)的題型，給大家做了兩種方式的解答，希望能幫助到你。

一般情況下都是筆試或者是直接上機(jī)操作，題型一般都是：如果字符串 s 中的字符循環(huán)移動(dòng)任意位置之后能夠得到另一個(gè)字符串 t，那么 s 就被稱為 t 的回環(huán)變位（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.

關(guān)于解答方面，我給在這里給出了2種方式：
解法一：
將s拆分成左右兩部分，然后另令s'=右+左，遍歷所有情況。如果是回環(huán)字符串的話，其中會(huì)有 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的后角標(biāo)的界限
      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));
}

以上就是基本快速的兩種解決方式，關(guān)于這個(gè)問(wèn)題，再給大家看一篇很詳細(xì)的判斷字符串回環(huán)變位解決思路：

如果字符串s中的字符循環(huán)移動(dòng)任意位置之后能夠得到另一字符串t，那么s就被稱為t的回環(huán)變位。例如，ACTGACG 就是 TGACGAC 的一個(gè)回環(huán)變位，反之亦然。判定這個(gè)條件在基因組序列中的研究是十分重要的。編寫(xiě)一個(gè)算法檢查兩個(gè)給定的字符串s和t是否互為回環(huán)變位。

這是我在《算法（第四版）》里看到的一道練習(xí)題 ，當(dāng)時(shí)的第一想法就是遍歷字符串 t，從不同的索引位置將字符串t分解成兩個(gè)子串，交換順序拼接后再與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;
  }

后來(lái)看答案，提示說(shuō)可以用一行代碼就能搞定了。當(dāng)時(shí)想了想，感覺(jué)不太可能，就作罷了。今天重新開(kāi)始學(xué)習(xí)這本書(shū)的時(shí)候，再次看到這道題，突然有了想法代碼如下：

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

解釋：如果字符串s和t互為回環(huán)變位，則s可分解為“AB”，t可分解為“BA”。那么t與自身拼接后則為“BABA”，顯然是會(huì)包含s的。這種思路比較巧妙，當(dāng)然了，自認(rèn)為算法效率并沒(méi)有什么提高。

為什么大家都會(huì)對(duì)這個(gè)經(jīng)典的JAVA問(wèn)題困惑著？最主要的原因就是解題的思路問(wèn)題：

容易想復(fù)雜的"回環(huán)變位"，思路錯(cuò)誤，問(wèn)題就會(huì)復(fù)雜化，一起來(lái)看下經(jīng)典的誤區(qū)和最終想明白以后的解法。

題目描述很簡(jiǎn)單:
如果字符串s重的字符循環(huán)移動(dòng)任意位置之后能夠得到另一個(gè)字符串t，那么s就被成為s的回環(huán)變位（circular rotation） 舉例省略…
問(wèn)題：請(qǐng)編寫(xiě)一個(gè)程序檢查2個(gè)給定的字符串s和t是否互為回環(huán)變位。
提示:判斷條件只需要一行代碼

看到題目當(dāng)時(shí)滿腦子想的都是雙重循環(huán)啊，游標(biāo)移動(dòng)啊各種i,j,k……
結(jié)果來(lái)一句這樣的提示，當(dāng)時(shí)我就受不了了，決定去看一下答案….

答案是這樣的

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

乍一看，好像真的可以…頓時(shí)鄙視了自己的各種游標(biāo)循環(huán)i,j,k…
（雖然可能底層也是各種循環(huán)游標(biāo)i,j,k,但是別人都實(shí)現(xiàn)了的基類直接用明顯更省事…）

但是也發(fā)現(xiàn)自己對(duì)String類的concat函數(shù)和indexOf的各種重載不懂

一下是jdk文檔的描述

public String concat(String str)將指定字符串連接到此字符串的結(jié)尾。 
如果參數(shù)字符串的長(zhǎng)度為 0，則返回此 String 對(duì)象。否則，創(chuàng)建一個(gè)新的 String 對(duì)象，用來(lái)表示由此 String 對(duì)象表示的字符序列和參數(shù)字符串表示的字符序列連接而成的字符序列。

示例： 

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

參數(shù)：
str - 連接到此 String 結(jié)尾的 String。 
返回：
一個(gè)字符串，它表示在此對(duì)象字符后連接字符串參數(shù)字符而成的字符。

public int indexOf(String str)返回指定子字符串在此字符串中第一次出現(xiàn)處的索引。返回的整數(shù)是 
 this.startsWith(str, k)
 為 true 的最小 k 值。 

參數(shù)：
str - 任意字符串。 
返回：
如果字符串參數(shù)作為一個(gè)子字符串在此對(duì)象中出現(xiàn)，則返回第一個(gè)這種子字符串的第一個(gè)字符的索引；如果它不作為一個(gè)子字符串出現(xiàn)，則返回 -1。

關(guān)于這個(gè)問(wèn)題，已經(jīng)在上文章闡述的非常清楚了，大家如果對(duì)此還有任何的疑問(wèn)，可以在本文下方留言討論。

最新評(píng)論