Viiisit [LeetCode] - 791. Custom Sort String

keep learning, keep coding!

Problem - Custom Sort String

You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously.

Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.

Return any permutation of s that satisfies this property.

翻譯蒟蒻

給定兩個字串，order 為先前以某種自訂順序排序過的唯一字元集合。題目要求重新排列字串 s 中的字元，使其符合 order 的排序方式。換句話說，如果一個字元 x 在 order 中出現在字元 y 之前，則在重新排列後的字串中，x 應該在 y 之前出現。未出現在 order 中的字元可以以任意順序出現，只要已出現在 order 中的字元保持其原始順序即可。

---

• Example 1:

  Input:  order = "cba", s = "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.

• Example 2:

  Input:  order = "bcafg", s = "abcd" 
  
  Output:  "bcad" 
  
  Explanation: The characters "b", "c", and "a" from order dictate the order for the characters in s. The character "d" in s does not appear in order, so its position is flexible.
  
  Following the order of appearance in order, "b", "c", and "a" from s should be arranged as "b", "c", "a". "d" can be placed at any position since it's not in order. The output "bcad" correctly follows this rule. Other arrangements like "bacd" or "bcda" would also be valid, as long as "b", "c", "a" maintain their order.

---

Solution - JavaScript

/**
 * @param {string} order
 * @param {string} s
 * @return {string}
 */
var customSortString = function(order, s) {
    let map = new Map()
    for (let i = 0; i < order.length; i++) {
        map.set(order[i], i)
    }
    let splitS = s.split('')
    splitS.sort((a, b) => {
      let aIndex = map.get(a) !== undefined ? map.get(a) : -1;
      let bIndex = map.get(b) !== undefined ? map.get(b) : -1;
      return aIndex - bIndex;
    })

    return splitS.join('')
};

Solution - Ruby

Solution 1:

def custom_sort_string(order, s)
  map = {}
  order.each_char.with_index do |c, i|
      map[c] = i
  end
  split_s = s.split("")
  split_s.sort! do |a, b|
    (map[a] || -1) <=> (map[b] || -1)
  end
  split_s.join
end

Solution 2:

def custom_sort_string(order, s)
  order_index = {}
  order.each_char.with_index do |c, i|
      order_index[c] = i
  end
    
  s.chars.sort_by { |char| order_index[char] || order.size }.join
end

這裡使用了 sort_by 方法，以 order_index[char] || order.size 取得 order 中的索引位置，如果不在 order 中，則返回 order.size，這樣可以使不在 order 中的字被排到最後面。

Solution - PHP

function customSortString($order, $s) {
  $map = [];
  for ($i = 0; $i < strlen($order); $i++){
      $map[$order[$i]] = $i;
  }
  $s = str_split($s);
  usort($s, function($a, $b) use ($map) {
      $aIndex = $map[$a] !== null ? $map[$a] : strlen($order);
      $bIndex = $map[$b] !== null ? $map[$b] : strlen($order);
      return $aIndex - $bIndex;
  });
  return implode('', $s);
}

PHP 方法筆記

• usort 函數用於 array 進行自定義排序的內置函數。。

  函數的基本語法如下：

  usort(array &$array, callable $callback): bool
  
  // array 是要排序的陣列，通過引用（&）傳遞，也就是排序後的結果會直接影響到原始的陣列。

  <!-- 按照字串長度升序排序 -->
  function compareLength($a, $b) {
      return strlen($a) - strlen($b);
  }
  
  $array = ["apple", "banana", "orange", "grape"];
  
  <!-- 使用 usort() 函數進行排序 -->
  usort($array, "compareLength");
  
  <!-- 輸出排序後的結果 -->
  print_r($array);
  <!-- Array
  (
      [0] => apple
      [1] => grape
      [2] => banana
      [3] => orange
  ) -->

LeetCode 傳送門 - Custom Sort String