読者です 読者をやめる 読者になる 読者になる

Cracking The Coding Interview (つづき)

前回記事にした

をちまちまと読み進めています。 こういう頭を使う知的ゲームは、なんというか大学受験の時の数学を思い出しますねー。
問題文を一読して解法の当たりがつくこともあれば,頭のなかで試行錯誤しながら正解に近づいて行く場合もあります。
一方で「全然解答がわからない。発想が根本的にちがうのでは?」という状況もあったり。
勉強していて一番面白いのはそういう問題を考えているときで、たとえ正解にたどり着かなくても解答を読んだ時のインパクトが違う。
今日は「そんな解き方、考え方があったのか!」と思わず膝を打った問題についてです。


1.8 片方の文字列がもう片方の文字列の一部分になっているかどうか調べるメソッドisSubstring()が使えると仮定する。
二つの文字列 str1 , str2 が与えられたとき、isSubstring()を一度だけ使ってstr2がstr1を回転させたものかどうか判定する
プログラムを書け


この問題を見たとき、全く解法が頭に浮かびませんでした。
「ふーむ、困った。どうしよう。とりあえず二つの文字列の長さが異なる場合は明らかにFalseでいいだろう」
「長さが同じ場合、str1とstr2の関係としては
①str1を回転させたものがstr2 ②str1とstr2は長さが同じだけで全然違う文字列 ③str1とstr2は互いにアナグラム
という場合が考えられそうだ」
「①は③に包含される。とりあえず②の可能性をつぶすためにアナグラムかどうか判定しよう」
アナグラムの判定はstr1とstr2をソートして比較すれば実装できるからとりあえずおいておこう」
「じゃあstr1とstr2が互いにアナグラムだとして、str1を回転させたらstr2になるかどうかどうやって判定しよう」
「str1をn回右に回転させたものがstr2だとしよう。いま文字列を右にn回回転させる関数をRotate(str,n)とすると  isSubstring(Rotate(str,n),str2) == True となるはずだ。」
「じゃあstr1を何回右回転させたらstr2になるのかどうやって求めたらいいだろう???」
「たとえば文字列中に一回しか出現しない文字cが存在するならstr1.indexOf(c)とstr2.indexOf(c)を比べれば回転数nが求められるだろう」
「そんな都合のいい文字cが存在しない場合は??」
「どうしよう....」
  ・
  ・
  ・

模範解答

模範解答をみてまず思ったのが「あれ?解説とソースコード短くね?」ということ。
実際数えるとソースコードのステップ数はたった10ステップ。一体どういうことだってばよ...
うすうす気づいていましたが考え方が根本的に違っていました。
この問題を解くために重要な考えは回転すなわち円運動には周期が存在するということです。 もっとかみ砕くと、繰り返しの中にパターンがあるということです。 例えば以下のような文字列str1,str2があったとします。

str1 = "waterbottle"
str2 = "erbottlewat"

str1を三回左に回転させたものがstr2になります。
では、実際にstr1を繰り返します

str1 + str1  == "waterbottlewaterbottle"

ここにstr2が含まれているのに気が付くでしょうか?

"waterbottlewaterbottle"

このように回転の周期性のために、元の文字を繰り返した中に回転後の文字列を見出すことができます。 というわけで答えは

isRotate(String str1,String str2){
   int len = str1.length();
   if(len == str2.length() && len > 0){
     String str11 = str1+str1;
     return isSubstring(str11,str2);
   }
   return false;
}

いやーこんな冴えたやり方があったとは。こういうのを自分で思いつけるようになりたいですな。