[LeetCode] #791 Custom Sort String (Medium)
LeetCode 第 791 題 Custom Sort String，難度 Medium
用 PHP 解 LeetCode 系列，Custom Sort String，屬於 Medium
原始題目
order and str are strings composed of lowercase letters. In order, no letter occurs more than once.
order was sorted in some custom order previously. We want to permute the characters of str so that they match the order that order was sorted.
More specifically, if x occurs before y in order, then x should occur before y in the returned string.
Return any permutation of str (as a string) that satisfies this property.
Note:
orderhas length at most26, and no character is repeated inorder.strhas length at most200.orderandstrconsist of lowercase letters only.
Example:
Input:
order = "cba"
str = "abcd"
Output: "cbad"
Explanation:
"a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a".
Since "d" does not appear in order, it can be at any position in the returned string.
"dcba", "cdba", "cbda" are also valid outputs.
題目分析
order指定了特定字母之間的順序- 輸入的
str如果包含order的字母，則要照順序排列 - 不在
order中的剩餘字母則直接接到整理好的字串後面後回傳
解題過程
看起來很簡單，但是實際開始解才發現要考慮的細節很多！
第一次解題看到範例輸入的 order = "cba", str = "abcd"
直覺就是把 order 遍歷一遍，找尋每一個字母有沒有出現在 str 裡面？
有的話存進結果字串，並且從 str 字串中移除該字母
最後再將 str 剩下的字母，也就是不在 order 字串中的字母們補上
這樣的確可以完成這個 testcase 的預期結果 Output = "cbad"
下一組輸入是 order = "cbafg", str = "abcd"，並期望得到 Output = "cbad" 也通過了
class Solution {
/**
* @param String $order
* @param String $str
* @return String
*/
function customSortString($order, $str) {
$order_array = str_split($order);
$str_array = str_split($str);
foreach($order_array as $char) {
$key = array_search($char, $str_array);
if ( ! ($key == false)) {
$result .= $char;
unset($str_array[$key]);
}
}
$result .= implode('', $str_array);
return $result;
}
}
事情沒有這麼簡單！下一組輸入是 order = "kqep", str = "pekeq"，期望得到 Output = "kqeep"
但是依照這個邏輯我們回傳了 Output = "kqepe"，因為 str 中 e 出現了兩次！
而我們遍歷的 order 只有一個 e
如此遍歷 order 是不可行了，題目說 order 每個字母最多出現一次，於是轉換思路改為遍歷輸入字串 str
- 首先遍歷輸入字串
str - 判斷當前字母是不是存在
order字串中 - 若有則存入一個二維陣列，該陣列的第一維是該字母在
order字串中的位置
使用二維陣列是為了處理str字串中字母重複出現的情境 - 若該字母不存在
order中，則存入剩餘字串的變數中 - 將剛剛的二維陣列依照第一維的值(在
order中的順序)排序，由小到大(必須保留鍵值) - 遍歷二維陣列的每一組字母集合，將其串成字串，並串上剩餘字串
於是這個 testcase 就通過了！以下是完成之後的完整程式碼
class Solution {
/**
* @param String $order
* @param String $str
* @return String
*/
function customSortString($order, $str) {
$order_array = str_split($order);
$str_array = str_split($str);
$result_array = [];
$result = '';
$else_char = '';
foreach($str_array as $char) {
if (in_array($char, $order_array)) {
$key = array_search($char, $order_array);
$result_array[$key][] = $char;
} else {
$else_char .= $char;
}
}
ksort($result_array);
foreach ($result_array as $char_nub) {
$result .= implode($char_nub);
}
$result .= $else_char;
return $result;
}
}
結果
