iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 5
0
自我挑戰組

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

【從面試題學邏輯-5】CTCI 1.2 如何判斷兩個字串是否互為排列組合

題目:
寫一個方法來判斷兩個字串是否為彼此的排列組合

舉例:
如果給了"cat""tac",就應該拿到true,因為這兩個字串只是排列組合
而如果給了tigerpanda,就應該拿到false,因為這兩個彼此不是排列組合


老樣子的提醒時間:

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


那就開始運用上一篇看到的方法解題吧!
由於這是運用上一篇看到的解法來小試身手,如果還沒有看過上一篇,建議先閱讀一下上一篇喔!

讓我們先解析一下題目的需求:

  • 排列組合就是兩個字串中,用到的字元種類、數量都一樣,像teaeat互相是排列組合
  • 兩個字串如果長度不同,絕對不會是彼此的排列組合,所以我們可以預先檢查字串的長度,如果不一樣就直接回false來省時間

當然也是可以運用先轉成陣列,排序後再比較,這個解法已經提過,故這邊只放程式碼

static boolean isPermutation(String s1, String s2) {
	if(s1.length()!=s2.length()) return false;
	char[] s1Arr = s1.toCharArray();
	char[] s2Arr = s2.toCharArray();
	Arrays.sort(s1Arr);
	Arrays.sort(s2Arr);
	for(int i = 0 ; i < s1.length() ; i++) {
		if(s1Arr[i] != s2Arr[i]) return false;
	}
	return true;
}

接下來我們運可以運用陣列來記錄字元是否出現過,那與上一題不一樣的是,上一題是單純紀錄「是否出現過」就好,而這一題需要紀錄「出現次數」,所以我們必須要改用int陣列

目前為止我們可以得出這段程式碼:

static boolean isPermutation(String s1, String s2) {
	if(s1.length()!=s2.length()) return false;
	int[] chars = new int[128];
}

再來我們要先把字串1出現的字元、出現次數儲存進陣列內
所以程式碼會變成這樣:

static boolean isPermutation(String s1, String s2) {
	if(s1.length()!=s2.length()) return false;
	int[] chars = new int[128];
	for(int i = 0 ; i < s1.length() ; i++) {
		chars[s1.charAt(i)]++;
	}
}

接下來要處理字串2,可能大家會想到另外開一個陣列儲存字串2,再來比較兩個陣列。但其實可以運用一個小撇步來省空間與時間:

反過來思考!(from Day3)
如果沒讀過Day3的文章,歡迎前往閱讀喔!

我們可以直接在字串1的陣列用「減法」的方式,儲存兼比對字串2,大家可以把陣列內的東西當成「在字串2應該要出現的次數」。

假設陣列內是[ 1 , 0 , 2 ](示範原因只取3個數,請大家當作他們是abc),代表說字串1出現了1個a、0個b、1個c,如果字串2要是字串1的排列組合,代表字串2也要出現1個a、0個b、1個c

所以說,我們把陣列代表是「在字串2應該要出現的次數」,字串2的字元每出現一次,就把對應位置的數字-1,如果是排列組合,最終陣列應該要是[ 0 , 0 , 0 ]

那如何同時比對呢?每次減完我們可以檢查一次數字是不是小於0,如果等於0,代表說這個字元在字串1與字串2出現的次數相同(加同樣次數 & 減同樣次數)。如果出現負數,代表這個字元出現在字串2的次數,大於出現在字串1的次數(應該很好懂,故這邊不多解釋了XD)。

而如果整個迴圈跑完,代表都沒有出現負數,而因為字串1與字串2的長度相同,代表整個字串內已經都是0了!
(假設字串1在陣列內加了10次的1,字串2也在陣列內減了10次的1,如此想像一下就會懂嘍!)

最終我們可以得到這段程式碼:

static boolean isPermutation(String s1, String s2) {
	if(s1.length()!=s2.length()) return false;
	int[] chars = new int[128];
	for(int i = 0 ; i < s1.length() ; i++) {
		chars[s1.charAt(i)]++;
	}
	for(int i = 0 ; i < s2.length() ; i++) {
		chars[s2.charAt(i)]--;
		if(chars[s2.charAt(i)] < 0) return false; 
	}
	return true;
}

一樣請注意:以上是在ASCII的情況下,如果不是就要更動陣列大小


恭喜!我們成功綜合前幾天的方法來解一道新的題目/images/emoticon/emoticon07.gif


上一篇
【從面試題學邏輯-4】CTCI 1.1 檢查字串內是否有重複字元
下一篇
【從面試題學邏輯-6】檢查單字大小寫是否合理(leetcode 520. Detect Capital)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言