一次寻找邻居单词列表的算法优化 | Tim's Blog


一次寻找邻居单词列表的算法优化 | Tim's Blog
定义一个单词的邻居为,与其长度相同,有且仅有一个字母不同的其他单词。对于一个单词列表,计算所有单词的邻居列表。
例如:单词sonsun为邻居,而与song不为邻居,因为它们长度不一样。
读者朋友们,看完这道题目后,请先进行独立思考,然后再展开阅读。p.s. 本文将不包含具体代码。

暴力法

第一个想法很直白,遍历所有单词,判断彼此是否为邻居,若为邻居,则将彼此加入到自己的邻居列表。
这个算法的复杂度为。n为单词的个数。当单词超过一万时,意味着有一亿次的邻居查找操作。
即使邻居判定的方法再高效,这个方法也是十分低效的。
请读者暂停阅读,思考一下如何优化。

第一次优化

根据邻居的定义,可知长度不同的单词一定不是邻居,所以对长度不同的单词的互相判断是否为邻居其实是不必要的。
可以先对单词列表进行一次预处理,将长度相同的单词放入到同一个列表中,然后对每一个这样的列表内进行彼此邻居的判定。
假设所有单词的长度可以均分为10份,则每一个列表的长度可约等n/10,整个的复杂度为,虽然还是,但是已经比之前的暴力法要高效好几倍。
已经考虑到这一步的同学请再次暂停,思考有无数量级上提升的解决方案。

第二次优化

由于第一次优化并没有将实质性的复杂度降低,所以在单词很多的情况下还是比较低效。
我们需要重新审题,看能不能发现一点什么。
了解正则表达式的同学都知道,s?n这个匹配可以匹配son,也可以匹配sun。也就是说s?nsonsun的共同匹配。而?un则是sungun的共同匹配。
邻居单词之间都有某种联系,这种联系就是它们都有一个共同的匹配。所以,我们可以遍历所有单词,建立以匹配为,匹配的单词列表为的字典,然后遍历每个匹配的单词列表,这些单词列表中的所有单词都互相为对方的邻居单词。
例如:
  1. 当遍历到单词sun时,sun有三个匹配,[?un, s?n, su?]。匹配字典中将加入这几个匹配,这时候字典的内容为{ ?un=>[sun], s?n=>[sun], su?=>[sun] }
  2. 当遍历到单词son时,son有三个匹配,[?on, s?n, so?]。匹配字典中将加入这几个匹配,这时候字典的内容为{ ?un=>[sun], s?n=>[sun, son], su?=>[sun], ?on=>[son], so?=>[son] }。其中,sonsun共同的匹配s?n对应的列表加入了son
  3. 当遍历到单词gun时,gun有三个匹配,[?un, g?n, gu?]。匹配字典中将加入这几个匹配,这时候字典的内容为{ ?un=>[sun, gun], s?n=>[sun, son], su?=>[sun], ?on=>[son], so?=>[son], g?n=>[gun], gu?=>[gun] }。其中,sungun共同的匹配?un对应的列表加入了gun
对于每一个单词,假设单词的长度为L,则单词有L个匹配。对于n个单词,则最多有n*L个匹配列表。假设最长的匹配列表的长度为m,则整个算法的复杂度为。由于每个单词的邻居不会太多,所以基本可以将m视为常数。所以整个算法的复杂度为
如果当单词列表长度n远大于最长单词的长度L时,这个算法的复杂度将为,线性时间。
其中本文的最后一个算法与第二章的变位词算法有相似之处。都是基于标识(索引)来解决问题。
而解决问题的关键在于发现问题可以用标识来解决,即邻居间的共性是存在一个共同的匹配,而每个单词的匹配都是有限的(跟单词的长度一致)
Read full article from 一次寻找邻居单词列表的算法优化 | Tim's Blog

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts