Force deduction solution summary - Sword finger offer II 114 Alien dictionary

Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

There is an alien language using English letters , The alphabetical order of this language is different from that of English .

Given a list of strings words , As a dictionary of this language ,words The string in has Sorted alphabetically in the new language .

Please restore the known alphabetical order in this language according to the dictionary , and In alphabetical order array . If there is no legal alphabetical order , return "" . If there are more than one possible legal alphabetical order , Return to it Any one Order is enough .

character string s Dictionary order is less than character string t There are two situations ：

At the first different letter , If s The letters in this alien language are in the alphabetical order of t Before the middle letter , that  s The dictionary order of is less than t .
If the previous min(s.length, t.length) The letters are the same , that s.length < t.length when ,s The dictionary order is also less than t .
 

Example 1：

Input ：words = ["wrt","wrf","er","ett","rftt"]
Output ："wertf"
Example 2：

Input ：words = ["z","x"]
Output ："zx"
Example 3：

Input ：words = ["z","x","z"]
Output ：""
explain ： There is no legal alphabetical order , Therefore return "" .
 

Tips ：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] It's only made up of lowercase letters

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/Jf1JuT
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  This difficult question , The question of time is not finished , I just thought about a general idea and wrote .
*  First, recursively , Find out all the dependencies . such as a stay b front , be a Of HashSet Add b.
*  All the dependencies that come out of this .
*  Then sort by Topology  +  Depth first search , To derive the correct string .

Code ：

public class Solution114 {
    // Unfinished 
    public String alienOrder(String[] words) {
        HashSet<Character>[] sets = new HashSet[26];
        for (int i = 0; i < 26; i++) {
            sets[i] = new HashSet<>();
        }
        searchRely(0, Arrays.asList(words), sets);
        return "";
    }

    private void searchRely(int index, List<String> words, HashSet<Character>[] sets) {
        if (words.size() == 0) {
            return;
        }
        char lastChar = 0;
        ArrayList<String> newList = new ArrayList<>();
        for (int i = 0; i <= words.size(); i++) {
            if (i == words.size()) {
                searchRely(index + 1, newList, sets);
                break;
            }
            String str = words.get(i);
            char c = str.charAt(index);
            if (lastChar == 0) {
                lastChar = c;
                newList.add(str);
                continue;
            }
            if (c != lastChar) {
                sets[c - 'a'].add(lastChar);
                lastChar = c;
                searchRely(index + 1, newList, sets);
                newList.clear();
            } else {
                newList.add(str);
            }
        }
    }
}