# [LeetCode 791. Custom Sort String](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3813/)
### Daily challenge Jul 17, 2021 (MEDIAN)

>**`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.

:::info
**Example 1:**
**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.
:::

:::warning
**Constraints:**
* order has length at most 26, and no character is repeated in order.
* str has length at most 200.
* order and str consist of lowercase letters only.
:::

---

### Approach 1 : Brute Force :bulb:
**`0 ms`**
計算 `str` 中元素出現的頻率。
再根據 `order` 的順率先將元素存入 `ans`，最後將還未放入的元素依序存入。

class Solution {
public:
    string customSortString(string order, string str) {
        // ASCII : a = 97
        map<char, int> list;
        int count[26];    
        bool used[26];
        
        memset(count, 0, sizeof(count));
        memset(used, false, sizeof(used));
        
        // count frequency of str[i]
        for(int i=0; i<str.length(); i++){
            count[str[i]-97]++;
        }

        string ans;
        // char[i] which appear in 'order' inserts to ans
        for(int i=0; i<order.size(); i++){
            for(int j=0; j<count[order[i]-97]; j++){
                ans += order[i];
                used[order[i]-97] = true;
            }
        }
        
        // insert other char[i] to ans
        for(int i=0; i<26; i++){
            if(!used[i]){
                for(int j=0; j<count[i]; j++){
                    ans += char(i+97);
                }
            }
        }

        return ans;
    }
};

### Approach 2 : Custom Compare Function :book:
**`0 ms`**

:::warning
using compare function in class need to add **static**.
:::

class Solution {
public:
    static string list;
    
    static bool cmp(const char a, const char b){
        return list.find(a) < list.find(b);
    }
    
    string customSortString(string order, string str) {
        // custom compare
        list = order;
        string ans = str;
        sort(ans.begin(), ans.end(), cmp);
        
        return ans;
    }
};
string Solution :: list;

### Approach 3 : Lambda Expression (C++11) :book:
**`0 ms`**

class Solution {
public: 
    string customSortString(string order, string str) {
        // custom lambda expression
        string ans = str;
        sort(ans.begin(), ans.end(), [&](char a, char b) { return order.find(a) < order.find(b); });
        
        return ans;
    }
};