[CodeWars] 解題：Simple Fun #116: Prime String

This is a 6kyu Kata on CodeWars (https://www.codewars.com), that I used to practice programing skill.

Codewars 是我在走跳的刷題網站，相關介紹請參考透過 codewars 修練 Swift 解題技巧 by @彼得潘的 iOS App Neverland

上面的題目分為最簡單的 8 kyu 到最難的 1 kyu，送交答案之後就可以看到其他 Code Warriors 不同的解法和各種奇思妙想。

今天來談談這讓我徹夜難眠的一題：難度 6 kyu 的 Simple Fun #116: Prime String

為了練習初學的 JavaScript 語法，解這題大約花了我 4 個小時，可以說是嚴重卡關。飯吃不下，覺睡不著，熬到好不容易解完，才開心了幾秒，看見大家票選的 Best practice，那優雅的解法一字一字映入眼簾，彼時我的內心震動，良久不能自已。

『這就是我和世界的差距？』

劇透警告！本帖含有解答說明，如果你看過題目後希望自己先嘗試挑戰，請謹慎服用。 spoiler alert! Do not read down if you want to solve this kata by yourself.

Prime 代表質數的意思，除了 1 以外不能被任何數整除，以此延伸來看題目的 "Prime String" 就很容易理解題意，我們的任務是要定義一個方法 primeString() 檢查輸入的字串是否由連續的重複字串組合而成（意即能被某字串”整除“）：

例如 "abcd" 就是個『質數字串』，而 "xyxy" 則否（"xyxy" = "xy" + "xy"）。

待測試的輸入會是英文小寫字母，輸出要求回傳布林值，如果是質數字串則回傳 true。

簡單測試長得像這樣：

console.log(primeString("asdf")); // should be true
console.log(primeString("abac")); // should be true
console.log(primeString("qiuefgqiuefgqiuefg")); // should be false
console.log(primeString("zkvjhuj")); // should be true

我的方法我的邏輯是將輸入字串中的某個字元作為分割陣列的符號，將其拆成具有某種規律的陣列，例：

'qiuefgqiuefgqiuefg'.split('q') // [ '', 'iuefg', 'iuefg', 'iuefg' ]

如此將第一個空元素去掉即可得到整齊的陣列，如果沒有重複的接著統計陣列中每個元素的數量，如果每個元素出現的次數都完全相同，就代表此輸入字串可以被整除。

function primeString(s) {
  // 將字串重複的部份切成一個規律的陣列
  let spArr = s.split(s[0]);
  // 切掉不要的頭部空元素
  spArr.shift();

  // 宣告 不重複計數器
  let falseCount = 0;

  //  將各個元素和它們出現的次數存成 key-value pair
  let tCounter = {};
  spArr.forEach(x => { tCounter[x] = (tCounter[x] || 0) + 1; });
  
  // 將每個元素的重複出現次數清點過後比較，如果出現的次數相同表示有重複
  for(let e of spArr) {
    // 如果重複次數小於等於 1 表示開頭字母只出現一次，其餘都不重複 falseCount + 1
    // 或者有任何元素的出現次數和陣列第一個元素不同 falseCount + 1
    (tCounter[spArr[0]] <= 1) || (tCounter[spArr[0]] !== tCounter[e]) ? falseCount += 1: e;
  };
  // 將不重複計數器 falseCount 轉為布林值輸出，大於 0 就會轉成 true
  return !!falseCount;
}

我的作法大約要 10 行，來看看大家選出的 Best practices：

The most Clever

In JavaScript

function primeString(s) {
  return (s + s).indexOf(s, 1) == s.length;
}

In Ruby

def primeString(s)
  (s + s).index(s, 1) == s.size
end

舉個例子 "steven" 字串長度為 6，其中各個字母的 index 則是 0 ~ 5，

s	t	e	v	e	n
0	1	2	3	4	5

這個解法先將字串變成兩倍長，並從 index 1 號位置開始找尋比對原始的字串：

s	t	e	v	e	n	s	t	e	v	e	n
0	1	2	3	4	5	6	7	8	9	10	11
	⇧	~	~	~	~	s	t	e	v	e	n

可以看到如果以『質數字串』下去比對，一定會在正好等於原始字串長度的位置(index 6)比對出來。

如果輸入 "xyxy" 則會在 index = 2 的位置找到：

x	y	x	y	x	y	x	y
0	1	2	3	4	5	6	7
	⇧	x	y	x	y	-	-

如果熟悉使用正規表達式，用群組的方式反向比對也是很快：

In JavaScript

function primeString(s) {
  return !/^(.+)\1+$/.test(s)
}

In Ruby

def prime_string(s)
  s !~ /^(.+)(\1+)$/
end

stevencch99/[CodeWars] 解題：Simple Fun #116: Prime String.md

[CodeWars] 解題：Simple Fun #116: Prime String