791. Custom Sort String(791. Custom Sort String)

一拿到这道题,我首先想的是用binary search做,但是因为结果String的长度不是固定的,用binary search很难实现。所以我写了第一个brute force的算法,时间复杂度是O(n2), 效率很低,beat 5%,而且很容易考虑不到edge case而出错。

    Map<Character, Integer> map = new HashMap<>();

    public String customSortString(String order, String s) {
        for (int i = 0; i < order.length(); i++) {
            map.put(order.charAt(i), i);
        }
        StringBuilder res = new StringBuilder();
        res.append(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!map.containsKey(c))
                res.append(c);
            else
                search(res, c, map);
        }
        return res.toString();
    }

    private void search(StringBuilder s, char c, Map<Character, Integer> map) {
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            if (!map.containsKey(temp) || map.get(temp) < map.get(c))
                continue;
            else if (map.get(temp) >= map.get(c)) {
                s.insert(i, c);
                return;
            }
        }
        s.append(c);
    }

这道题是求字符串里的对字符的sort,我们还可以利用bucket sort来做,首选把s放在bucket,再用order做sort,最后再把那些没有在order里面的字符加到字符串上即可,时间复杂度O(n), 算法如下:

public String customSortString_bucketsort(String order, String s) {    int[] bucket = new int[26];    for (int i = 0; i < s.length(); i++) {        int c = s.charAt(i);        bucket[c - 'a']++;    }    StringBuilder res = new StringBuilder();    for (int i = 0; i < order.length(); i++) {        int index = order.charAt(i) - 'a';        for (int j = 0; j < bucket[index]; j++) {            res.append((char) (index + 'a'));        }        bucket[index] = 0;    }    for (int i = 0; i < bucket.length; i++) {        for (int j = 0; j < bucket[i]; j++) {            res.append((char) (i + 'a'));        }    }    return res.toString();}
————————

As soon as I got this question, I first thought about using binary search, but because the length of the result string is not fixed, it is difficult to use binary search. So I wrote the first brute force algorithm. The time complexity is O (N2), the efficiency is very low, beat 5%, and it is easy to make mistakes without considering the edge case.

    Map<Character, Integer> map = new HashMap<>();

    public String customSortString(String order, String s) {
        for (int i = 0; i < order.length(); i++) {
            map.put(order.charAt(i), i);
        }
        StringBuilder res = new StringBuilder();
        res.append(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!map.containsKey(c))
                res.append(c);
            else
                search(res, c, map);
        }
        return res.toString();
    }

    private void search(StringBuilder s, char c, Map<Character, Integer> map) {
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            if (!map.containsKey(temp) || map.get(temp) < map.get(c))
                continue;
            else if (map.get(temp) >= map.get(c)) {
                s.insert(i, c);
                return;
            }
        }
        s.append(c);
    }

This problem is to find the sort of characters in the string. We can also use bucket sort. First put s in the bucket, then order to sort, and finally add those characters that are not in the order to the string. The time complexity is O (n). The algorithm is as follows:

public String customSortString_bucketsort(String order, String s) {    int[] bucket = new int[26];    for (int i = 0; i < s.length(); i++) {        int c = s.charAt(i);        bucket[c - 'a']++;    }    StringBuilder res = new StringBuilder();    for (int i = 0; i < order.length(); i++) {        int index = order.charAt(i) - 'a';        for (int j = 0; j < bucket[index]; j++) {            res.append((char) (index + 'a'));        }        bucket[index] = 0;    }    for (int i = 0; i < bucket.length; i++) {        for (int j = 0; j < bucket[i]; j++) {            res.append((char) (i + 'a'));        }    }    return res.toString();}