上周面的，一周后接到HR电话说过啦 为onsite攒人品！
是一个大叔，上来就说我们做一道题，然后你可以问问我和谷歌有关的问题。
题目：word extension。 面经题
Assumption: regular words contain 2 or fewer of the same chars in a row, and word extensions contain 3 or more of the smae char in a row.
Given an input string, represting a word, write a method to finds the start and end indices of all extensions in the word.
“hellooooo” -> [(4,8)]
“helllooooo” -> [(2,4), (5,9)]
写完之后让我想几个corner case， 我问数字标点可不可以出现，比如“666!!!”, 大小写区不区分，比如 “zZZZzzz"，还有的corner case就是“hahahahaha"，这种同一字符超过2个但不是 in a row的，再有就是最普遍的空字符串“”。
然后follow up:
Assume that you have an API is_dictionar_word(s): returns True if the word s is in the dictionary.
Write a method: bool is_extended_dictionary_word(s) which returns:
True if is_dictionary_word(s) == True
True if you collapse all the extensions in the word, and it is a dictionary word
False otherwise
is_dictionary_word(“xyz”)->False
is_extended_dictionary_word(“xyz”)->False
is_dictionary_word(“hello”) ->True
is_extended_dictionary_word(“helloooo”)->True
可以用之前那部分写的函数返回的s中extention的indices。用DFS解的，问时间的复杂度，答2^m (m是s中extension的数量)，因为一个extension可以collpase成一个字母或两个字母，都要试一下是不是is_dictionary_word。
中间过程有些紧张，有点卡，大叔人还挺好说你先和我说思路，代码之后再慢慢写。