> 一份2021年03月25日的信息流提炼 ### 每天学点算法 #### 一道微软面试题 > Given a dictionary of words and a string made up of those words (no spaces), return the original sentence in a list. If there is more than one possible reconstruction, return any of them. If there is no possible reconstruction, then return null. 给定一个单词字典和由这些单词组成的字符串(没有空格)返回列表中的原句。如果有多个可能的重构,返回其中任何一个。如果没有可能的重构,则返回null。 例如,给定一组单词'quick'、'brown'、'the'、'fox',以及字符串 "thequickbrownfox",你应该返回['the'、'quick'、'brown'、'fox']。 给定一组词'bed','bath','bath','and','beyond',以及字符串 "bedbathandbeyond",返回['bed','bath','and','beyond']或['bath','and','beyond']。 ```go package main import ( "fmt" "strings" "sort" ) func main() { str := "thequickbrownfox" arr := []string{"quick", "brown", "the", "fox"} result_map := map[int]string {} result_index := []int{} // store word index for _, v := range arr { if strings.Index(str,v) >= 0 { result_index = append(result_index, strings.Index(str,v)) result_map[strings.Index(str,v)] = v } } // sort index sort.Ints(result_index) result := make([]string, 0, len(result_map)) // store result for _,v := range result_index { result = append(result, result_map[v]) } fmt.Println(result) } ``` [gist上的python解法](https://gist.github.com/folksilva/dd8ff13c3e1d5c7c117cf9ee18859dcc) ```python def reconstruction(words, s): words = set(words) res = [] n = len(s) i = j = 0 while j < n: if s[i:j+1] in words: res.append(s[i:j+1]) i = j + 1 else: if j == n - 1: return None j += 1 return res dictionary = ['bed', 'bath', 'bedbath', 'and', 'beyond'] word = 'bedbathandbeyond' result = [['bed', 'bath', 'and', 'beyond'], ['bedbath', 'and', 'beyond']] assert reconstruction(dictionary, word) in result dictionary = ['quick', 'brown', 'the', 'fox'] word = 'thequickbrownfox' result = [['the','quick','brown','fox']] assert reconstruction(dictionary, word) in result dictionary = ['quick', 'the', 'fox'] word = 'thequickbrownfox' assert reconstruction(dictionary, word) is None ``` ### 其他值得阅读 #### 关于用户体验设计的有力名言 原文:[13 powerful quotes about UX design (& what you can learn from them)](https://dribbble.com/stories/2021/03/18/ux-quotes) - UI是马鞍、马镫和缰绳。UX是你能够骑马的感觉。— Dain Miller - 有些人认为设计意味着外观。但如果你深入了解,会发现它其实是关于如何工作的。Some people think design means how it looks. But of course, if you dig deeper, it’s really how it works. --Steve Jobs - 想让你的用户爱上你的设计?爱上你的用户吧。— Dana Chisnell - 易用性可能是无形的,但它的缺失肯定不是。Ease of use may be invisible, but its absence sure isn’t. — IBM - 用户体验的经验法则:选择越多,问题越多。Rule of thumb for UX: More options, more problems. — Scott Belsky - 如果我们希望用户喜欢我们的软件,我们就应该把它设计成一个讨人喜欢的人:尊重、慷慨、乐于助人。If we want users to like our software, we should design it to behave like a likable person: respectful, generous, and helpful. — Alan Cooper - 如果我有一个小时的时间来解决一个问题,而我的生命取决于这个问题的解决,我会用前55分钟的时间来决定提出一个适当的问题,因为一旦我知道了适当的问题,我就可以在不到5分钟的时间里解决这个问题。**If I had an hour to solve a problem and my life depended on the solution, I would spend the first 55 minutes determining the proper question to ask, for once I know the proper question, I could solve the problem in less than five minutes.** — Albert Einstein - 设计并不是制作一个漂亮的、有质感的、有令人惊叹的动画的button。而是要想出是否有办法完全摆脱button。— Edward Tufte - 当程序的行为完全按照用户的想法进行时,用户界面就设计得很好。A user interface is well-designed when the program behaves exactly how the user thought it would. — Joel Spolsky