leetcode: 269. The Martian Dictionary

题目来源

• leetcode：269. 火星词典

题目描述

现有一种使用英语字母的火星语言,这门语言的字母顺序与英语顺序不同.

给你一个字符串列表 words ,作为这门语言的词典,words 中的字符串已经 按这门新语言的字母顺序进行了排序 .

请你根据该词典还原出此语言中已知的字母顺序,并 按字母递增顺序 排列.若不存在合法字母顺序,返回 “” .若存在多种可能的合法字母顺序,返回其中 任意一种 顺序即可.

字符串 s 字典顺序小于 字符串 t 有两种情况：

• 在第一个不同字母处,如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前,那么 s 的字典顺序小于 t .
• 如果前面 min(s.length, t.length) 字母都相同,那么 s.length < t.length 时,s 的字典顺序也小于 t .

示例 1：

输入：words = [“wrt”,“wrf”,“er”,“ett”,“rftt”]
输出：“wertf”
示例 2：

输入：words = [“z”,“x”]
输出：“zx”
示例 3：

输入：words = [“z”,“x”,“z”]
输出：“”
解释：不存在合法字母顺序,因此返回 “” .

提示：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成

思路

思路

• 可以先根据word生成一张图
  • 比较相邻两个words,Compare the two one by onewordscharacters in the same position,until you find a position where the first character is not the same
  • Two characters in this position we can get valid information,That is, these two characters are therealien orderrelative order in
  • It should be noted that this position is also useful,We can't get any information because of the different locations behind.
• Then look at topological sort,不能有环

举个例子

比如题目中给的例子1,There are sequential relationships that can be deduced

t->f
w->e
r->t
e->r

实现

class Solution {
    
public:
    std::string alienOrder(vector<std::string>& words) {
    
       if(words.empty()){
    
           return "";
       }

       int N = words.size();
       // Sets the in-degree of the characters that appear to be 0
       // Letters that do not appear have an in-degree of -1,The in-degree of an occurrence of a letter is non-negative
       std::map<char, int> indegree;
        for (int i = 0; i < N; ++i) {
    
            for(char ch : words[i]){
    
                indegree[ch] = 0;
            }
        }

        std::map<char, std::set<char>> graph;
        for (int i = 0; i < N - 1; ++i) {
    
            std::string curr = words[i];
            std::string next = words[i + 1];
            int len = std::min(curr.length(), next.length());
            int j = 0;
            for(;j < len; j++){
    
                // # Save the first different character order,The letter in front is askey,The letters located at the back are storedsetas the value
                if(curr[j] != next[j]){
    
                   if(!graph[curr[j]].count(next[j])){
    
                       graph[curr[j]].emplace(next[j]);
                       indegree[next[j]]++;
                   }
                   break;
                }
            }
            // a The alphabetical order of  b,then in the given dictionary a will appear first b 前面
            if(j < curr.length() && j == next.length()){
    
                return "";  //前面都一样,curcharacters are longer,next没有字符了----The dictionary given is not correct
            }
        }

        std::queue<char> q;
        for(auto it : indegree){
    
            char key = it.first;
            if(indegree[key] == 0){
    
                q.push(key);
            }
        }

		std::string ans;
        while (!q.empty()){
    
            char curr = q.front(); q.pop();
            ans += curr;
            if(graph.count(curr)){
    
                for(char next : graph[curr]){
    
                    --indegree[next];
                    if(indegree[next] == 0){
    
                        q.push(next);
                    }
                }
            }
        }

        return ans.length() == indegree.size() ? ans : "";
    }
};

测试

int main() {
    
    std::vector<std::string> vec {
    "wrt",
                                  "wrf",
                                  "er",
                                  "ett",
                                  "rftt"};

    Solution a;
    auto v =  a.alienOrder(vec) ;
    printf("%s\n", v.c_str());
    return 1;
}

参考

• leetcode269.火星词典「拓扑排序」