Brooke

一、題目

In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.

 

Example 1:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" Output: true Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2:

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz" Output: false Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

Example 3:

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz" Output: false Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

 

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 20
• order.length == 26
• All characters in words[i] and order are English lowercase letters.

 

二、程式作法

第二次撰寫

public class Solution
{
    public bool IsAlienSorted(string[] words, string order)
    {
        int maxLength = words[0].Length;
        for (int i = 1; i < words.Length; i++)
            maxLength = Math.Max(maxLength, words[i].Length);

        int j = 0;
        while (j < maxLength)
        {
            bool contin = false;
            for (int i = 0; i < words.Length - 1; i++)
            {
                int a0, a1;
                if (j >= words[i].Length)
                    a0 = -1;
                else
                    a0 = GetSquence(words[i][j], order);

                if (j >= words[i + 1].Length)
                    a1 = -1;
                else
                    a1 = GetSquence(words[i + 1][j], order);

                if (a0 > a1) return false;
                if (a0 == a1) contin = true;
            }
            if (!contin) return true;
            j++;
        }

        return true;
    }

    public int GetSquence(char c, string order)
    {
        for (int i = 0; i < 26; i++)
            if (order[i] == c) return i;
        return -1;
    }
}

 

第一次撰寫

public class Solution
{
    public char[] dic = Array.Empty<char>();
    public bool IsAlienSorted(string[] words, string order)
    {
        if (words.Length == 1)
            return true;

        //initial
        dic = order.ToCharArray();
        char[][] wordCollection = new char[words.Length][];
        for (int i = 0; i < words.Length; i++)
            wordCollection[i] = words[i].ToCharArray();

        //process           
        for (int i = 0; i < wordCollection.Length - 1; i++)
        {
            int idx = 0;
            do
            {
                int curr = -1, next = -1;
                curr = (wordCollection[i].Length <= idx) ? -1 : FindOrder(wordCollection[i][idx]);
                next = (wordCollection[i + 1].Length <= idx) ? -1 : FindOrder(wordCollection[i + 1][idx]);

                if (curr > next)
                    return false;

                if (i == wordCollection.Length - 1 - 1 && curr < next)
                    return true;

                idx++;
            } while (idx < wordCollection[i].Length || idx < wordCollection[i + 1].Length);
        }

        return true;
    }

    public int FindOrder(char a)
    {
        for (int i = 0; i < dic.Length; i++)
            if (dic[i] == a)
                return i;

        return -1;
    }
}

 

三、思路筆記

題目要的是驗證所有字串中是否皆依照指定字母排序，來做排序。

每次比較當所有的字串的開頭是按照順序的，為符合第一個排序要件；

而上述中如發生有相同字母之字串，那些字串還要再比出個高下，

以上要件都符合才算是「有排序」的。

這一題我沒有做的很好，列出了好幾個測試案例，

但到後來才邊寫邊測出規則，筆記也亂到不知道在寫什麼，雖然程式是蠻簡潔可以看的懂啦。