Nine Chapter
  • Introduction
    • Summary
  • 1.Binary Search
    • Introduction
    • 458.Last position of target
    • 600.Smallest Rectangle Enclosing Black Pixels
    • 585.Maximum Number in Mountain Sequence
    • 183.Wood Cut
    • 62.Search in Rotated Sorted Array
    • 63.Search in Rotated Sorted Array II
    • 159.Find Minimum in Rotated Sorted Array
    • 160.Find Minimum in Rotated Sorted Array II
    • 75.Find Peak Element
    • 60.Search Insert Position
    • 28.Search a 2D Matrix
    • 240. Search a 2D Matrix II
    • 14.First Position of Target
    • 74.First Bad Version
    • 875. Koko Eating Bananas
    • 1011. Capacity To Ship Packages Within D Days (M)
    • 410. Split Array Largest Sum (H)
    • 475. Heaters (M)
    • 1044. Longest Duplicate Substring (H)
  • 2.Binary Tree
    • Summary
      • 二叉树八股文:递归改迭代
      • BST
      • Frame
    • 66.Binary Tree Preorder Traversal
    • 67.🌟Binary Tree Inorder Traversal
    • 145. Binary Tree Postorder Traversal (E)
    • 98.Validate Binary Search Tree(M)
    • 85.Insert Node in a Binary Search Tree
    • 104. Maximum Depth of Binary Tree(E)
    • 235. Lowest Common Ancestor of a Binary Search Tree (E)
    • 236.Lowest Common Ancestor of Binary Tree(M)
    • 578.Lowest Common Ancestor III
    • 1120.Subtree with Maximum Average
    • 596.Minimum Subtree
    • 480.Binary Tree Paths
    • 453.Flatten Binary Tree to Linked List
    • 110.Balanced Binary Tree
    • 376.Binary Tree Path Sum
    • 246.Binary Tree Path Sum II
    • 475.Binary Tree Maximum Path Sum II
    • 124.Binary Tree Maximum Path Sum (H)
    • Path Sum (*)
      • 112. Path Sum
      • 113. Path Sum II
      • 437. Path Sum III
    • 177.Convert Sorted Array to Binary Search Tree With Minimal Height
    • 7.Binary Tree Serialization
    • 72,73.Construct Binary Tree
    • Binary Search Tree Path
    • 245.Subtree
    • 469.Identical Binary Tree
    • 87.Remove Node in Binary Search Tree
    • 116.Populating Next Right Pointers in Each Node (M)
    • 114. Flatten Binary Tree to Linked List(M)
    • 654.Maximum Binary Tree (M)
    • 105. 🌟Construct Binary Tree from Preorder and Inorder Traversal (M)
    • 106. Construct Binary Tree from Inorder and Postorder Traversal (M)
    • 652. Find Duplicate Subtrees(M)
    • 230. Kth Smallest Element in a BST (M)
    • 538&1038. Convert BST to Greater Tree
    • 450. Delete Node in a BST (M)
    • 701. Insert into a Binary Search Tree (M)
    • 96. Unique Binary Search Trees
    • 95. Unique Binary Search Trees II (M)
    • 1373. Maximum Sum BST in Binary Tree (H)
    • 297. Serialize and Deserialize Binary Tree (H)
    • 222. Count Complete Tree Nodes (M)
    • 1120. Maximum Average Subtree
    • 341. Flatten Nested List Iterator
    • 333. Largest BST Subtree (M)
    • 543. Diameter of Binary Tree
    • Binary Tree Longest Consecutive Sequence(*)
      • 298.Binary Tree Longest Consecutive Sequence
      • 549. Binary Tree Longest Consecutive Sequence II (M)
  • 3.Breadth First Search
    • Introduction
      • BFS 算法解题套路框架
      • 双向 BFS 优化
    • 102.Binary Tree Level Order Traversal (M)
    • 103. Binary Tree Zigzag Level Order Traversal (M)
    • 107.Binary Tree Level Order Traversal II(M)
    • 618.Search Graph Nodes
    • 207.Course Schedule (M)
    • 210.Course Schedule II (M)
    • 611.Knight Shortest Path
    • 598.Zombie in Matrix
    • 133.Clone Graph (M)
    • 178.Graph Valid Tree
    • 7.Binary Tree Serialization
    • 574.Build Post Office
    • 573.Build Post Office II
    • 127.Topological Sorting
    • 127.Word Ladder
    • 126. Word Ladder II
    • (LeetCode)515.Find Largest Value in Each Tree Row
    • 111. Minimum Depth of Binary Tree (E)
    • 752. Open the Lock
    • 542. 01 Matrix (M)
    • 1306. Jump Game III (M)
  • 4.Depth First Search+BackTracking
    • Summary
      • FloodFill 算法
    • 136.Palindrome Partitioning
    • 39.Combination Sum
    • 40.Combination Sum II
    • 377. Combination Sum IV
    • 77.Combinations (M)
    • 78.Subsets (M)
    • 90.Subsets II (M)
    • 46.🌟Permutations
    • 47.Permutations II
    • 582.Word Break II
    • 490.The Maze (M)
    • 51.N-Queens (H)
    • 52. N-Queens II (H)
    • 698. Partition to K Equal Sum Subsets (M)
    • 22. Generate Parentheses (M)
    • 岛屿问题
      • 200.Number of Islands (M)
      • 1254. Number of Closed Islands (M)
      • 1020. Number of Enclaves (M)
      • 695. Max Area of Island (M)
      • 1905. Count Sub Islands (M)
      • 694. Number of Distinct Islands
    • 131. Palindrome Partitioning (M)
    • 967. Numbers With Same Consecutive Differences (M)
    • 79. Word Search (M)
    • 212. Word Search II (M)
    • 472. Concatenated Words (H)
    • Page 2
    • 291. Word Pattern II
    • 17. Letter Combinations of a Phone Number (M)
  • 5.LinkedList
    • Summary
      • 单链表的倒数第 k 个节点
      • Merge two/k sorted LinkedList
      • Middle of the Linked List
      • 判断链表是否包含环
      • 两个链表是否相交 Intersection of Two Linked Lists
      • 递归反转链表
      • 如何判断回文链表
    • 599.Insert into a Cyclic Sorted List
    • 21.Merge Two Sorted Lists (E)
    • 23.Merge k Sorted Lists (H)
    • 105.Copy List with Random Pointer
    • 141.Linked List Cycle (E)
    • 142.Linked List Cycle II (M)
    • 148.Sort List (M)
    • 86.Partition List (M)
    • 83.Remove Duplicates from Sorted List(E)
    • 82.Remove Duplicates from Sorted List II (M)
    • 206.Reverse Linked List (E)
    • 92.Reverse Linked List II (M)
    • 143.Reorder List (M)
    • 19.Remove Nth Node From End of List (E)
    • 170.Rotate List
    • 🤔25.Reverse Nodes in k-Group (H)
    • 452.Remove Linked List Elements
    • 167.Add Two Numbers
    • 221.Add Two Numbers II
    • 876. Middle of the Linked List (E)
    • 160. Intersection of Two Linked Lists (E)
    • 234. Palindrome Linked List (E)
    • 2130. Maximum Twin Sum of a Linked List (M)
  • 6.Array
    • Summary
      • 前缀和思路PrefixSum
      • 差分数组 Difference Array
      • 双指针Two Pointers
      • 滑动窗口算法算法
      • Sliding windows II
      • 二分搜索Binary Search
      • 排序算法
      • 快速选择算法
    • 604.Window Sum
    • 138.Subarray Sum
    • 41.Maximum Subarray
    • 42.Maximum Subarray II
    • 43.Maximum Subarray III
    • 620.Maximum Subarray IV
    • 621.Maximum Subarray V
    • 6.Merge Two Sorted Arrays
    • 88.Merge Sorted Array
    • 547.Intersection of Two Arrays
    • 548.Intersection of Two Arrays II
    • 139.Subarray Sum Closest
    • 65.Median of two Sorted Arrays
    • 636.132 Pattern
    • 402.Continuous Subarray Sum
    • 303. Range Sum Query - Immutable (E)
    • 304.Range Sum Query 2D - Immutable (M)
    • 560. Subarray Sum Equals K (M)
    • 370. Range Addition(M)
    • 1109. Corporate Flight Bookings(M)
    • 1094. Car Pooling (M)
    • 76. Minimum Window Substring(H)
    • 567. Permutation in String (M)
    • 438. Find All Anagrams in a String(M)
    • 3. Longest Substring Without Repeating Characters (M)
    • 380. Insert Delete GetRandom O(1) (M)
    • 710. Random Pick with Blacklist (H)
    • 528. Random Pick with Weight (M)
    • 26. Remove Duplicates from Sorted Array (E)
    • 27. Remove Element (E)
    • 283. Move Zeroes (E)
    • 659. Split Array into Consecutive Subsequences (M)
    • 4. Median of Two Sorted Arrays (H)
    • 48. Rotate Image (M)
    • 54. Spiral Matrix (M)
    • 59. Spiral Matrix II (M)
    • 918. Maximum Sum Circular Subarray
    • 128. Longest Consecutive Sequence (M)
    • 238. Product of Array Except Self (M)
    • 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (M)
    • 1151. Minimum Swaps to Group All 1's Together (M)
    • 2134. Minimum Swaps to Group All 1's Together II
    • 2133. Check if Every Row and Column Contains All Numbers
    • 632. Smallest Range Covering Elements from K Lists (H)
    • 36. Valid Sudoku (M)
    • 383. Ransom Note
    • 228. Summary Ranges
  • 7.Two pointers
    • Summary
      • Two Sum
      • 2Sum 3Sum 4Sum 问题
    • 1.Two Sum I
    • 170.Two Sum III - Data structure design
    • 167.Two Sum II- Input array is sorted
    • 609.Two Sum - Less than or equal to target
    • 610.Two Sum - Difference equals to targe
    • 587.Two Sum - Unique pairs
    • 533.Two Sum - Closest to target
    • 443.Two Sum - Greater than target
    • 653. Two Sum IV - Input is a BST (M)
    • 57.3Sum
    • 59.3Sum Closest
    • 58.4Sum
    • 148.Sort Colors
    • 143.Sort Colors II
    • 31.Partition Array
    • 625.Partition Array II
    • 382.Triangle Count
      • 611. Valid Triangle Number
    • 521.Remove Duplicate Numbers in Array
    • 167. Two Sum II - Input Array Is Sorted (E)
    • 870. Advantage Shuffle (M)
    • 9. Palindrome Number (E)
    • 125. Valid Palindrome(E)
    • 5. Longest Palindromic Substring (M)
    • 42. Trapping Rain Water
    • 11. Container With Most Water (M)
    • 658. Find K Closest Elements (M)
    • 392. Is Subsequence
  • 8.Data Structure
    • Summary
      • 数据结构的存储方式
      • 单调栈
      • 单调队列
      • 二叉堆 Binary Heap
      • TreeMap
      • TreeSet
      • 🌟Trie
      • Trie Application
    • 155. Min Stack (E)
    • 716. Max Stack (E)
    • 1648. Sell Diminishing-Valued Colored Balls
    • 232. Implement Queue using Stacks (E)
    • 225. Implement Stack using Queues(E)
    • 84.Largest Rectangle in Histogram
    • 128.Hash Function
    • Max Tree
    • 544.Top k Largest Numbers
    • 545.Top k Largest Numbers II
    • 613.High Five
    • 606.Kth Largest Element II
    • 5.Kth Largest Element
    • 129.Rehashing
    • 4.Ugly Number II
    • 517.Ugly Number
    • 28. Implement strStr()
    • 594.strStr II
    • 146.LRU Cache
    • 460.LFU Cache
    • 486.Merge k Sorted Arrays
    • 130.Heapify
    • 215. Kth Largest Element in an Array (M)
    • 612.K Closest Points
    • 692. Top K Frequent Words
    • 347.Top K Frequent Elements
    • 601.Flatten 2D Vector
    • 540.Zigzag Iterator
    • 541.Zigzag Iterator II
    • 423.Valid Parentheses
    • 488.Happy Number
    • 547.Intersection of Two Arrays
    • 548.Intersection of Two Arrays II
    • 627.Longest Palindrome
    • 638.Strings Homomorphism
    • 138.Subarray Sum
    • 647.Substring Anagrams
    • 171.Anagrams
    • 739. Daily Temperatures(M)
    • 496. Next Greater Element I (E)
    • 503. Next Greater Element II(M)
    • 316. Remove Duplicate Letters(M) & 1081. Smallest Subsequence of Distinct Characters
    • 239. Sliding Window Maximum (H)
    • 355. Design Twitter (M)
    • 895. Maximum Frequency Stack (H)
    • 20. Valid Parentheses (E)
    • 921. Minimum Add to Make Parentheses Valid (M)
    • 1541. Minimum Insertions to Balance a Parentheses String (M)
    • 32. Longest Valid Parentheses (H)
    • Basic Calculator (*)
      • 224. Basic Calculator
      • 227. Basic Calculator II (M)
    • 844. Backspace String Compare
    • 295. Find Median from Data Stream
    • 208. Implement Trie (Prefix Tree)
    • 461.Kth Smallest Numbers in Unsorted Array
    • 1152.Analyze user website visit pattern
    • 811. Subdomain Visit Count (M)
    • 71. Simplify Path (M)
    • 362. Design Hit Counter
  • 9.Dynamic Programming
    • Summary
      • 最优子结构 Optimal Sustructure
      • 子序列解题模板
      • 空间压缩
      • 背包问题
        • Untitled
      • 股票买卖问题
      • KMP
    • 109.Triangle
    • 110.Minimum Path Sum
    • 114.Unique Paths
    • 115.Unique Paths II
    • 70.Climbing Stairs
    • 272.Climbing StairsII
    • 116.Jump Game
    • 117.Jump Game II
    • 322.Coin Change
    • 518. Coin Change 2 ()
    • Backpack I~VI
      • LintCode 563.Backpack V (M)
    • Best Time to Buy and Sell Stock(*)
      • 121. Best Time to Buy and Sell Stock
      • 122. Best Time to Buy and Sell Stock II (M)
      • 123. Best Time to Buy and Sell Stock III (H)
      • 188. Best Time to Buy and Sell Stock IV (H)
      • 309. Best Time to Buy and Sell Stock with Cooldown (M)
      • 714. Best Time to Buy and Sell Stock with Transaction Fee (M)
    • 394.Coins in a line
    • 395.Coins in a Line II
    • 509. Fibonacci Number (E)
    • 931. Minimum Falling Path Sum (M)
    • 494. Target Sum (M)
    • 72. Edit Distance (H)
    • 300.Longest Increasing Subsequence
    • 1143. Longest Common Subsequence (M)
    • 718. Maximum Length of Repeated Subarray
    • 583. Delete Operation for Two Strings (M)
    • 712. Minimum ASCII Delete Sum for Two Strings(M)
    • 53. Maximum Subarray (E)
    • 516. Longest Palindromic Subsequence (M)
    • 1312. Minimum Insertion Steps to Make a String Palindrome (H)
    • 416. Partition Equal Subset Sum (M)
    • 64. Minimum Path Sum(M)
    • 651. 4 Keys Keyboards (M)
    • House Robber (*)
      • 198. House Robber (M)
      • 213. House Robbber II
      • 337. House Robber III (M)
    • Word Break (*)
      • 139.Word Break (M)
    • 140. Word Break II (H)
    • 828. Count Unique Characters of All Substrings of a Given String (H)
    • 174. Dungeon Game (H)
    • 1567. Maximum Length of Subarray With Positive Product (M)
  • 10. Graph
    • Introduction
      • 有向图的环检测
      • 拓扑排序
      • 二分图判定
      • Union-Find
      • 最小生成树(Minimum Spanning Tree)算法
        • KRUSKAL 最小生成树算法
        • Prim 最小生成树算法
      • Dijkstra 最短路径算法
      • BFS vs DFS
    • 797. All Paths From Source to Target (M)
    • 785. Is Graph Bipartite? (M)
    • 886. Possible Bipartition (M)
    • 130. Surrounded Regions (M)
    • 990. Satisfiability of Equality Equations (M)
    • 721. Accounts Merge (M)
    • 323. Number of Connected Components in an Undirected Graph (M)
    • 261. Graph Valid Tree
    • 1135. Connecting Cities With Minimum Cost
    • 1584. Min Cost to Connect All Points (M)
    • 277. Find the Celebrity (M)
    • 743. Network Delay Time (M)
    • 1631. Path With Minimum Effort (M)
    • 1514. Path with Maximum Probability (M)
    • 589.Connecting Graph
    • 🌟787. Cheapest Flights Within K Stops (M)
    • 2050. Parallel Courses III (H)
    • 1293. Shortest Path in a Grid with Obstacles Elimination (H)
    • 864. Shortest Path to Get All Keys (H)
    • 269. Alien Dictionary (H)
    • 1192. Critical Connections in a Network (H)
    • 529. Minesweeper (M)
  • 11.Math
    • Page 1
Powered by GitBook
On this page

Was this helpful?

  1. 10. Graph

269. Alien Dictionary (H)

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

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: ""
Explanation: The order is invalid, so return "".

Constraints:

  • 1 <= words.length <= 100

  • 1 <= words[i].length <= 100

  • words[i] consists of only lowercase English letters.

Solution:

这题主要问题是题意理解,拓扑排序可以出货。

题意理解: 啥是words按照lexicographically,这对题有啥影响。 最初的错误理解: ab, ac 可以得出 a->b, a->c 这样的关系 其实正确的理解是 ab, ac 可以得出 b->c,因为ab,ac是按照字典序排列,a和a相等,所以考虑b和c,b排在c的前面,所以 b->c

题目的关键在于想明白单词之间的关系, 相邻的两个单词之前, 我们可以忽略掉他们的共同前缀, 当碰到到两个单词中出现不相同的字母(假设这两个单词是w和w'), 那么我们就在这两个字母中间连一条边, 同时将w'的入度+1

正确顺序建立完了graph和indegree,这个题应该解决了60%。

其次,啥是输出的时候按照lexicographically,对这题有啥影响。 如果同时在indegree==0的字符里出现了 b 和 c,先输出正常字典序最小的,所以这里使用最小堆很对口。

再其次,如果输出的order和原始字符数不一样,就是说某些字符没有拓扑序,输出空。

Note: Testcase: ["abc","ab"] ,expect output: ""

Testcase: ["ab","abc"] ,expect output: "abc"

class Solution {
    public String alienOrder(String[] words) {
        
        Map<Character, Set<Character>> graph = buildGraph(words);
        if (graph == null) {
            return "";
        }
        Map<Character, Integer> indegree = getIndegree(graph);
        return topologicalSorting(graph, indegree);
    }
    
    public Map<Character, Set<Character>> buildGraph(String[] words)
    {
        Map<Character, Set<Character>> graph = new HashMap<>();
        
        // create nodes
        for(int i = 0; i< words.length; i++)
        {
            for(int j = 0; j< words[i].length(); j++)
            {
                graph.putIfAbsent(words[i].charAt(j), new HashSet<>());
            }
        }
        
        // create edges
        for(int i = 0; i< words.length-1; i++)
        {
            String word1 = words[i];
            String word2 = words[i+1];
            int index = 0;
            int minLen = Math.min(word1.length(), word2.length());
            while(index < minLen && index < minLen)
            {
                if(word1.charAt(index) != word2.charAt(index))
                {
                    graph.get(word1.charAt(index)).add(word2.charAt(index));
                    break;
                }
                index++;
            }
            
            // Testcase: ["abc","ab"] ,expect output: ""
            if(index == minLen && word1.length() > word2.length())
            {
                return null;
            }
        }
        return graph;
    }
    
    
    public Map<Character, Integer> getIndegree(Map<Character, Set<Character>> graph)
    {
        Map<Character, Integer> indegree = new HashMap<>();
        
        for(Character from : graph.keySet())
        {
            indegree.put(from, 0);
        }
        
        for(Character from : graph.keySet())
        {
            for(Character to : graph.get(from))
            {
                indegree.put(to, indegree.get(to) + 1);
            }
        }
        
        return indegree;
    }
    
    
    public String topologicalSorting(Map<Character, Set<Character>> graph, Map<Character, Integer> indegree)
    {
        // as we should return the topo order with lexicographical order
        // we should use PriorityQueue instead of a FIFO Queue
        StringBuilder sb = new StringBuilder();
        Queue<Character> queue = new PriorityQueue<>();
        for(Character c : indegree.keySet())
        {
            if(indegree.get(c) == 0)
            {
                queue.offer(c);
            }
        }
        
        while(!queue.isEmpty())
        {
            Character current = queue.poll();
            sb.append(current);
            for(Character adj : graph.get(current))
            {
                indegree.put(adj, indegree.get(adj)-1);
                if(indegree.get(adj) == 0)
                {
                    queue.offer(adj);
                }
            }
        }
        
        //最后还要判断排出来的拓扑序是不是有效的, 是不是所有的节点都遍历过了
        //如果不是的话我们直接输出空串, 证明组成给定的这些单词的字母没有办法组成一个合理的拓扑序
        if(sb.length() != indegree.size())
        {
            return "";
        }
        return sb.toString();
    }
}

Previous864. Shortest Path to Get All Keys (H)Next1192. Critical Connections in a Network (H)

Last updated 3 years ago

Was this helpful?

就是当你的字典是的情况的时候, 最后的结果有可能不是字典序的(即输出可能是"bda", 因为哈希表是没有顺序的) 为了处理这种情况, 我们在进行BFS的时候, 应该使用PrioirtyQueue来保证输出的顺序

'bd', 'ba'