Skip to content

Files

Latest commit

3e47705 · Aug 24, 2024

History

History

0791.Custom Sort String

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Aug 24, 2024
Aug 24, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jun 21, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
comments difficulty edit_url tags
true
中等
哈希表
字符串
排序

English Version

题目描述

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

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" 遵循这一规则。其他排序如 "dbca" 或 "bcda" 也是有效的,只要维持 "b"、"c"、"a" 的顺序。

 

提示:

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

解法

方法一:自定义排序

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

时间复杂度 O ( m + n × log n ) ,空间复杂度 O ( m ) 。其中 m n 分别是字符串 o r d e r s 的长度。

Python3

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)))

Java

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());
    }
}

C++

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;
    }
};

Go

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)
}

TypeScript

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('');
}

Rust

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 中每个字符的出现次数,存储在 c n t 数组中。

然后把字符串 s o r d e r 中出现的字符按照 o r d e r 中的顺序排序,添加到结果字符串中。最后把剩余的字符直接追加到结果字符串中。

时间复杂度 O ( m + n ) ,空间复杂度 O ( m ) 。其中 m n 分别是字符串 o r d e r s 的长度。

Python3

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)

Java

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();
    }
}

C++

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;
    }
};

Go

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)
}

TypeScript

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('');
}

Rust

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
    }
}