Question

791. 自定义字符串排序

English Version

题目描述

给定两个字符串 order 和 s 。order 的所有字母都是 唯一 的，并且以前按照一些自定义的顺序排序。

对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符串中， x 也应该出现在 y 之前。

返回 _满足这个性质的 s 的任意一种排列 _。

 

示例 1:

输入: order = "cba", s = "abcd"
输出: "cbad"
解释: 
"a"、"b"、"c"是按顺序出现的，所以"a"、"b"、"c"的顺序应该是"c"、"b"、"a"。
因为"d"不是按顺序出现的，所以它可以在返回的字符串中的任何位置。"dcba"、"cdba"、"cbda"也是有效的输出。

示例 2:

输入: order = "cbafg", s = "abcd"
输出: "cbad"
解释：字符 "b"、"c" 和 "a" 规定了 s 中字符的顺序。s 中的字符 "d" 没有在 order 中出现，所以它的位置是弹性的。

按照出现的顺序，s 中的 "b"、"c"、"a" 应排列为"b"、"c"、"a"。"d" 可以放在任何位置，因为它没有按顺序排列。输出 "bcad" 遵循这一规则。其他排序如 "bacd" 或 "bcda" 也是有效的，只要维持 "b"、"c"、"a" 的顺序。

 

提示:

• 1 <= order.length <= 26
• 1 <= s.length <= 200
• order 和 s 由小写英文字母组成
• order 中的所有字符都 不同

解法

方法一：自定义排序

一种比较直接的思路是，用哈希表或数组 $d$ 记录字符串 $order$ 中每个字符的位置，然后对字符串 $s$ 中每个字符按照其在 $d$ 中的位置进行排序。如果某个字符不在 $d$ 中，我们可以将其位置置为 $0$。

时间复杂度 $O(m + n\times \log n)$，空间复杂度 $O(m)$。其中 $m$ 和 $n$ 分别是字符串 $order$ 和 $s$ 的长度。

class Solution:
  def customSortString(self, order: str, s: str) -> str:
    d = {c: i for i, c in enumerate(order)}
    return ''.join(sorted(s, key=lambda x: d.get(x, 0)))

class Solution {
  public String customSortString(String order, String s) {
    int[] d = new int[26];
    for (int i = 0; i < order.length(); ++i) {
      d[order.charAt(i) - 'a'] = i;
    }
    List<Character> cs = new ArrayList<>();
    for (int i = 0; i < s.length(); ++i) {
      cs.add(s.charAt(i));
    }
    cs.sort((a, b) -> d[a - 'a'] - d[b - 'a']);
    return cs.stream().map(String::valueOf).collect(Collectors.joining());
  }
}

class Solution {
public:
  string customSortString(string order, string s) {
    int d[26] = {0};
    for (int i = 0; i < order.size(); ++i) d[order[i] - 'a'] = i;
    sort(s.begin(), s.end(), [&](auto a, auto b) { return d[a - 'a'] < d[b - 'a']; });
    return s;
  }
};

func customSortString(order string, s string) string {
  d := [26]int{}
  for i := range order {
    d[order[i]-'a'] = i
  }
  cs := []byte(s)
  sort.Slice(cs, func(i, j int) bool { return d[cs[i]-'a'] < d[cs[j]-'a'] })
  return string(cs)
}

function customSortString(order: string, s: string): string {
  const toIndex = (c: string) => c.charCodeAt(0) - 'a'.charCodeAt(0);
  const n = order.length;
  const d = new Array(26).fill(n);
  for (let i = 0; i < n; i++) {
    d[toIndex(order[i])] = i;
  }
  return [...s].sort((a, b) => d[toIndex(a)] - d[toIndex(b)]).join('');
}

impl Solution {
  pub fn custom_sort_string(order: String, s: String) -> String {
    let n = order.len();
    let mut d = [n; 26];
    for (i, c) in order.as_bytes().iter().enumerate() {
      d[(c - b'a') as usize] = i;
    }
    let mut ans = s.chars().collect::<Vec<_>>();
    ans.sort_by(|&a, &b|
      d[((a as u8) - ('a' as u8)) as usize].cmp(&d[((b as u8) - ('a' as u8)) as usize])
    );
    ans.into_iter().collect()
  }
}

方法二：字符计数

我们还可以先统计 $s$ 中每个字符的出现次数，存储在 $cnt$ 数组中。

然后把字符串 $s$ 在 $order$ 中出现的字符按照 $order$ 中的顺序排序，添加到结果字符串中。最后把剩余的字符直接追加到结果字符串中。

时间复杂度 $O(m+n)$，空间复杂度 $O(m)$。其中 $m$ 和 $n$ 分别是字符串 $order$ 和 $s$ 的长度。

class Solution:
  def customSortString(self, order: str, s: str) -> str:
    cnt = Counter(s)
    ans = []
    for c in order:
      ans.append(c * cnt[c])
      cnt[c] = 0
    for c, v in cnt.items():
      ans.append(c * v)
    return ''.join(ans)

class Solution {
  public String customSortString(String order, String s) {
    int[] cnt = new int[26];
    for (int i = 0; i < s.length(); ++i) {
      ++cnt[s.charAt(i) - 'a'];
    }
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < order.length(); ++i) {
      char c = order.charAt(i);
      while (cnt[c - 'a']-- > 0) {
        ans.append(c);
      }
    }
    for (int i = 0; i < 26; ++i) {
      while (cnt[i]-- > 0) {
        ans.append((char) ('a' + i));
      }
    }
    return ans.toString();
  }
}

class Solution {
public:
  string customSortString(string order, string s) {
    int cnt[26] = {0};
    for (char& c : s) ++cnt[c - 'a'];
    string ans;
    for (char& c : order)
      while (cnt[c - 'a']-- > 0) ans += c;
    for (int i = 0; i < 26; ++i)
      if (cnt[i] > 0) ans += string(cnt[i], i + 'a');
    return ans;
  }
};

func customSortString(order string, s string) string {
  cnt := [26]int{}
  for _, c := range s {
    cnt[c-'a']++
  }
  ans := []rune{}
  for _, c := range order {
    for cnt[c-'a'] > 0 {
      ans = append(ans, c)
      cnt[c-'a']--
    }
  }
  for i, v := range cnt {
    for j := 0; j < v; j++ {
      ans = append(ans, rune('a'+i))
    }
  }
  return string(ans)
}

function customSortString(order: string, s: string): string {
  const toIndex = (c: string) => c.charCodeAt(0) - 'a'.charCodeAt(0);
  const count = new Array(26).fill(0);
  for (const c of s) {
    count[toIndex(c)]++;
  }
  const ans: string[] = [];
  for (const c of order) {
    const i = toIndex(c);
    ans.push(c.repeat(count[i]));
    count[i] = 0;
  }
  for (let i = 0; i < 26; i++) {
    if (!count[i]) continue;
    ans.push(String.fromCharCode('a'.charCodeAt(0) + i).repeat(count[i]));
  }
  return ans.join('');
}

impl Solution {
  pub fn custom_sort_string(order: String, s: String) -> String {
    let mut count = [0; 26];
    for c in s.as_bytes() {
      count[(c - b'a') as usize] += 1;
    }
    let mut ans = String::new();
    for c in order.as_bytes() {
      for _ in 0..count[(c - b'a') as usize] {
        ans.push(char::from(*c));
      }
      count[(c - b'a') as usize] = 0;
    }
    for i in 0..count.len() {
      for _ in 0..count[i] {
        ans.push(char::from(b'a' + (i as u8)));
      }
    }
    ans
  }
}