iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 8
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 8

【從面試題學邏輯-8】我又轉過來啦,我又轉過去啦,比我啊大大(CTCI 1.9 旋轉的字串)

字串與陣列系列的題目只到明天,下一部分將開始講位元運算(bitwise operation)

終於要進下一部分了嗎/images/emoticon/emoticon34.gif!?

今天是一題解決邏輯後,就非常簡單的字串題,話雖如此嘛……其實個人比較想歸類在後面的邏輯思考題,但想想這題的難度,還是放在起步的第一階段好了。不過後面的題目就會以LeetCode為主了,原因沒有別的-CTCI後面的題目可能一天講不完,不然就是強力勸退,讓我們趕緊來看看題目

題目:
請寫一個程式,來檢查輸入的兩個字串是否是其中一個經過旋轉後的樣子

舉例:
"keyboard""boardkey"互相是旋轉的關係(從key board中間切開旋轉)
"apple""grape"不是旋轉關係

大家可以想像旋轉是像下圖這樣,中間有一個轉軸,左右分別是字串的一部分

旋轉過後就會像這個樣子


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


當然最基本解就是把其中一串逐一切開來,選轉後看看兩者是否相同,但既然都走到這邊了,這個就不額外再提程式碼了

所以這題要怎麼解比較好呢?

剛剛我們在上面講了轉軸這件事情,所以兩者如果互為旋轉關係,那麼兩個字串應該會是:

  • part1+part2
  • part2+part1

對吧?接下來要放一張神奇的圖片來告訴大家怎麼做比較好

請看中間,是不是出現了一個part1+part2?所以只要把其中一個字串自己重複一次,就可以找到旋轉的自己了呢!/images/emoticon/emoticon42.gif

先上程式碼再進行解釋

static boolean isRotated(String s1, String s2) {
	if(s1.length() != s2.length()) return false;
        // 長度不同一定不是
	String s1s1 = s1 + s1;
	for(int i=0 ; i <= s1s1.length()-s1.length() ; i++) {
		if(s1s1.substring(i, i+s1.length()).equals(s2)) return true;
	}
	return false;
}

首先要認識一個方法:

  • substring(i, j):可以取出一個字串中指定的區域,就想像成去壽司店,指定要某條魚的肚子啦、尾巴之類的
  • 注意:substring()是從i開始到j結束,這個範圍包含i,但不含j喔,也就是說substring(0,2)會取出0 1 ,而不是0 1 2

因為我們要取相同長度來做比較,所以要取的範圍是0到s1s1-s1長度的地方(再往後就取不到規定長度的字串了),這邊把if內的東西拿出來排版一下

s1s1
    .substring(i, i+s1.length()) // 取出和s1長度相同的字串
    .equals(s2) // 檢查是否等於s2

結束!


明天會講陣列最後一題的旋轉陣列,然後終於要進到位元運算的單元啦!


上一篇
【從面試題學邏輯-7】如果在矩陣內玩炸彈威力滿點的炸彈超人的話…(CTCI 1.8 矩陣清道夫)
下一篇
【從面試題學邏輯-9】如何旋轉矩陣/二維陣列 ?到底是轉魔術方塊還是轉大腦?(CTCI 1.7 旋轉矩陣)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言