Commitef97199

authored

Update 269-Alien-Dictionary.py

1 parent80fd573 commitef97199Copy full SHA for ef97199

File tree

+22

-20

lines changed

+22

-20

lines changed

Lines changed: 22 additions & 20 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,37 +1,39 @@`
`1`	`1`	`classSolution:`
`2`	`2`	`defalienOrder(self,words:List[str])->str:`
`3`		`-adj= {char:set()forwordinwordsforcharinword}`
	`3`	`+adj= {c:set()forwinwordsforcinw}`
`4`	`4`
`5`	`5`	`foriinrange(len(words)-1):`
`6`	`6`	`w1,w2=words[i],words[i+1]`
`7`	`7`	`minLen=min(len(w1),len(w2))`
	`8`	`+`
`8`	`9`	`iflen(w1)>len(w2)andw1[:minLen]==w2[:minLen]:`
`9`	`10`	`return""`
	`11`	`+`
`10`	`12`	`forjinrange(minLen):`
`11`		`-ifw1[j]!=w2[j]:`
`12`		`-print(w1[j],w2[j])`
`13`		`-adj[w1[j]].add(w2[j])`
	`13`	`+w1[j]!=w2[j]:`
	`14`	`+adj[w1[j]].add(w2[j]]`
`14`	`15`	`break`
`15`	`16`
`16`		`-visited= {}# {char: bool} Falsevisited, Truecurrent path`
`17`		`-res= []`
	`17`	`+visit= {}# False=visited, True=current path`
	`18`	`+res= []`
`18`	`19`
`19`		`-defdfs(char):`
`20`		`-ifcharinvisited:`
`21`		`-returnvisited[char]`
	`20`	`+defdfs(c):`
	`21`	`+ifcinvisit:`
	`22`	`+returnvisit[c]`
	`23`	`+`
	`24`	`+visit[c]=True`
`22`	`25`
`23`		`-visited[char]=True`
	`26`	`+forneiinadj[c]:`
	`27`	`+ifdfs(nei):`
	`28`	`+returnTrue`
`24`	`29`
`25`		`-forneighCharinadj[char]:`
`26`		`-ifdfs(neighChar):`
`27`		`-returnTrue`
	`30`	`+visit[c]=False`
	`31`	`+res.append(c)`
`28`	`32`
`29`		`-visited[char]=False`
`30`		`-res.append(char)`
	`33`	`+forcinadj:`
	`34`	`+ifdfs(c):`
	`35`	`+return""`
`31`	`36`
`32`		`-forcharinadj:`
`33`		`-ifdfs(char):`
`34`		`-return""`
	`37`	`+return"".join(res)`
`35`	`38`
`36`		`-res.reverse()`
`37`		`-return"".join(res)`
	`39`	`+`

Comments

(0)