[1433] Check If a String Can Break Another String

判斷兩個字串的任意字母排列組合(permutation)是不是可以其中一個break另一個

break的意思是說 字串A 的 char[i] 都一定會 大於等於 字串B的char[i] (或是反之)

一開始就想說那是不是排序完去做就好了，結果還真的是 XD

但事情不是憨人想的那麼簡單 ，這樣去做太慢了！（為什麼XD）

所以原來要用counting sort啊（茶）(what?! 什麼是counting sort?! XD)

int comp(const void *a, const void *b)

{

return strcmp((char *)a , (char *)b);

}

bool checkUp(char *s1, char *s2, int len)

{

int i;

for (i=0;i<len;i++)

{

if (s1[i]>s2[i])

break;

}

return (i==len);

}

bool checkIfCanBreak(char * s1, char * s2){

int len= strlen(s1);

qsort(s1, len, sizeof(char), comp);

qsort(s2, len, sizeof(char), comp);

return (checkUp(s1, s2, len) | checkUp(s2, s1, len));

}

好吧於是counting sort也來一個 。但是我怎麼寫的好像有點醜XD

似乎可以用變數分別紀錄現在是A大還是B大，用一個迴圈跑完吧。

但我就喜歡分開處理，不行嗎XD！

bool checkUp(int *s1, int *s2)

{

int i;

int totalA=0;

int totalB=0;

for (i=0;i<26;i++)

{

totalA+=s1[i];

totalB+=s2[i];

if (totalA> totalB)

break;

}

return (i==26);

}

bool checkIfCanBreak(char * s1, char * s2){

int len= strlen(s1);

int countA[26];

int countB[26];

for (int i=0;i<26;i++)

{

countA[i]=0;

countB[i]=0;

}

for (int i=0;i<len;i++)

{

countA[s1[i]-'a']++;

countB[s2[i]-'a']++;

}

return (checkUp(countA, countB) | checkUp(countB, countA));

}