## 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<>());
}

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;
}
}