一隻箱子裡的貓,看著電腦螢幕

Schrödinger's Programmer

奔跑吧工程師,趁年輕跑得越遠越好

[LeetCode] #791 Custom Sort String (Medium)

LeetCode 第 791 題 Custom Sort String,難度 Medium

Ray

LeetCode #791 run result

用 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:

  • order has length at most 26, and no character is repeated in order.
  • str has length at most 200.
  • order and str consist 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.

題目分析

  1. order 指定了特定字母之間的順序
  2. 輸入的 str 如果包含 order 的字母,則要照順序排列
  3. 不在 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",因為 stre 出現了兩次!
而我們遍歷的 order 只有一個 e

如此遍歷 order 是不可行了,題目說 order 每個字母最多出現一次,於是轉換思路改為遍歷輸入字串 str

  1. 首先遍歷輸入字串 str
  2. 判斷當前字母是不是存在 order 字串中
  3. 若有則存入一個二維陣列,該陣列的第一維是該字母在 order 字串中的位置
    使用二維陣列是為了處理 str 字串中字母重複出現的情境
  4. 若該字母不存在 order 中,則存入剩餘字串的變數中
  5. 將剛剛的二維陣列依照第一維的值(在 order 中的順序)排序,由小到大(必須保留鍵值)
  6. 遍歷二維陣列的每一組字母集合,將其串成字串,並串上剩餘字串

於是這個 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;
    }
}

結果

result

最新文章

Category

Tag