## Monday, August 8, 2016

### Google – Longest String Pair that Forms a Cycle

Google – Longest String Pair that Forms a Cycle

GFG – Check if Strings can be Chained to Form a Cycle 可以算这题的一个follow up。这题用hash map就可以搞定了，但是GFG这题还是比较难的。
[Solution]

[Solution #1] – binary search

`// O(n^2) time, O(logn) space`
`class` `Solution {`
`  ``int` `result = ``0``;`

`  ``public` `int` `longestPair(String[] dict) {`
`    ``if` `(dict == ``null` `|| dict.length == ``0``) {`
`      ``return` `0``;`
`    ``}`

`    ``for` `(String word : dict) {`
`      ``String end = word.substring(word.length() - ``2``, word.length());`
`      ``char` `first = word.charAt(``0``);`
`      ``binarySearch(word, end, first, ``0``, dict.length - ``1``, dict);`
`    ``}`
`    ``return` `result;`
`  ``}`

`  ``private` `void` `binarySearch(String word, String start, ``char` `last, ``int` `l, ``int` `r, String[] dict) {`
`    ``if` `(l > r) {`
`      ``return``;`
`    ``}`

`    ``while` `(l <= r) {`
`      ``int` `mid = (l + r) / ``2``;`
`      ``String curr = dict[mid];`

`      ``if` `(curr.startsWith(start)) {`
`        ``if` `(curr.charAt(curr.length() - ``1``) == last) {`
`          ``result = Math.max(result, word.length() + curr.length());`
`        ``}`
`        ``binarySearch(word, start, last, l, mid - ``1``, dict);`
`        ``binarySearch(word, start, last, mid + ``1``, r, dict);`
`        ``return``;`
`      ``}`
`      ``else` `if` `(curr.substring(``0``, ``2``).compareTo(start) < ``0``) {`
`        ``l = mid + ``1``;`
`      ``}`
`      ``else` `{`
`        ``r = mid - ``1``;`
`      ``}`
`    ``}`
`  ``}`
`}`

`/*`
`  ``If the dict is not sorted, then HashMap is required`
`  ``O(n) time, O(n) space`
`*/`
`class` `Solution2 {`
`  ``public` `int` `longestPair(String[] dict) {`
`    ``if` `(dict == ``null` `|| dict.length == ``0``) {`
`      ``return` `0``;`
`    ``}`

`    ``Map<String, List<Integer>> map = ``new` `HashMap<>();`
`    ``for` `(``int` `i = ``0``; i < dict.length; i++) {`
`      ``String word = dict[i];`
`      ``int` `len = word.length();`
`      ``if` `(len <= ``2``) ``continue``;`
`      ``String key = word.substring(len - ``2``, len)  + word.charAt(``0``);`
`      ``map.putIfAbsent(key, ``new` `ArrayList<>());`
`      ``map.get(key).add(i);`
`    ``}`

`    ``int` `result = ``0``;`
`    ``for` `(``int` `i = ``0``; i < dict.length; i++) {`
`      ``String word = dict[i];`
`      ``int` `len = word.length();`
`      ``String _key = word.substring(``0``, ``2``) + word.charAt(word.length() - ``1``);`
`      ``if` `(map.containsKey(_key)) {`
`        ``for` `(``int` `j : map.get(_key)) {`
`          ``result = Math.max(result, len + dict[j].length());`
`        ``}`
`      ``}`
`    ``}`
`    ``return` `result;`
`  ``}`
`}`