[LeetCode] Custom Sort String

Problem: 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.

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.

Approach: We can just use the custom comparator while sorting the input string "str" using the indices of "order". It's a straight forward problem to solve which can be understood by just looking at the code.

Implementation in C#:

    public string CustomSortString(string order, string str) 

    {

        int [] orderArr = new int[26];

        for (int i = 0; i < order.Length; ++i)

        {

            orderArr[order[i] - 'a'] = i;

        }    

        char[] strArr = str.ToCharArray();

        Array.Sort(strArr, (x, y) => {

            return orderArr[x - 'a'].CompareTo( orderArr[y - 'a']);

        });

        return new string(strArr);

    }

Complexity: O ( m + nlogn) where m is length of order and n is length of str.