• 難度：中等
• Facebook 面試題

題目

給一個新的字母表晚凿，如 {c, b, a, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}社露，根據(jù)新的字母表排序字符串數(shù)組。

注意事項

• 輸入的單詞長度不超過 100偿荷。
• 輸入的單詞總數(shù)不超過 10000。
• 可以認為溉躲，輸入的新字母表即一個長度為 26 的字符串星岗。
• 保證題目只會出現(xiàn)小寫字母。

樣例

Sample Input:
"cbadefghijklmnopqrstuvwxyz"
["cab", "cba", "abc"]

Sample Output:
["cba", "cab", "abc"]

Sample Input:
"zbadefghijklmnopqrstuvwxyc"
["bca", "czb", "za", "zba", "ade"]

Sample Output:
["zba", "za", "bca", "ade", "czb"]

解答

這題理論上可以使用 std::sort 實現(xiàn)首有，這樣就只需要編寫一個比較函數(shù)即可燕垃。

不過這題似乎不能這么寫，于是只能手寫排序算法了

判斷字母在新字母表的位置可以用自帶的 find() 實現(xiàn)井联，代碼如下卜壕。

class Solution 
{
private:
    string newAlphabet;

    bool lessThan(const string &a, const string &b) 
    {
        auto p = a.begin(), q = b.begin();
        while(p != a.end() && q != b.end()) 
        {
            size_t posP = newAlphabet.find(*p), posQ = newAlphabet.find(*q);
            if(posP == posQ) 
            {
                ++p, ++q;
                continue;
            }
            else if(posP < posQ)
                return true;
            else
                return false;
        }
        if(p == a.end())
            return true;
        else
            return false;
    }

    void insertionSort(vector<string> &words, size_t left, size_t right) 
    {
        string temp;
        size_t p, j;
        for(p = left; p < right; p++) 
        {
            temp = words[p];
            for(j = p; j != 0 && lessThan(temp, words[j - 1]); j--)
                swap(words[j], words[j - 1]);
            words[j] = temp;
        }
    }

    void merge(vector<string> &words, size_t left, size_t mid, size_t right) 
    {
        vector<string> temp(right - left + 1);
        size_t p = left, q = mid, i = 0;
        while(p != mid && q != right) 
        {
            if(lessThan(words[p], words[q])) {
                temp[i++] = words[p];
                p++;
            }
            else 
            {
                temp[i++] = words[q];
                q++;
            }
        }
        while(p != mid)
            temp[i++] = words[p++];
        while(q != right)
            temp[i++] = words[q++];

        for(size_t j = 0; j < i; j++)
            words[left + j] = temp[j];
    }

    void mergeSort(vector<string> &words, size_t left, size_t right) 
    {
        if(right - left <= 10) 
        {
            insertionSort(words, left, right);
            return;
        }
        size_t mid = left + (right - left) / 2;
        mergeSort(words, left, mid);
        mergeSort(words, mid, right);
        merge(words, left, mid, right);
    }
public:
    /**
     * @param alphabet: the new alphabet
     * @param words: the original string array
     * @return : the string array after sorting
     */
    vector<string> wordSort(string &alphabet, vector<string> &words) {
        if(words.size() < 2)
            return words;
        newAlphabet = alphabet;
        mergeSort(words, 0, words.size());
        return words;
    }
};