Google – Longest String Pair that Forms a Cycle

Google – Longest String Pair that Forms a Cycle
给一个 sorted dictionary, [about, apple, google, leg, lemma, time]
要求返回最长的一对pair，使得Pair中的两个单词满足：
第一个单词的最后两个字母等于第二个单词的头两个
第二个单词的最后一个字母等于第一个单词的头一个
就相当于形成一个cycle。
GFG – Check if Strings can be Chained to Form a Cycle 可以算这题的一个follow up。这题用hash map就可以搞定了，但是GFG这题还是比较难的。
[Solution]
最直接的办法就是用一个hash table来hash头两个字母以及单词。然后遍历一遍dict找最长的pair。这种做法时间复杂度为O(n)，空间也为O(n)。
不过注意题目写了是sorted dictionary. 如果被问到有没有其他方法？自然会想到binary search.
如果再仔细想想这道题的binary search并不能优化时间复杂度，反而降低了。只有在空间上有所提升。
[Solution #1] – binary search
对于每个字典里的string，根据它的最后两个字母，在整个字典里做binary search。
但是当mid的头两个字母和curr的后两个字母一样时，不能直接丢掉左边或右边，得从mid开始往两边扫。所以这样binary search的时间复杂度为O(n), 即使用递归binary search, 递归式为T(n) = 2T(n / 2)，画个tree就知道也是O(n).
这样每个string做一遍binary search就是O(n^2).
不过递归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;

  }

}

Read full article from Google – Longest String Pair that Forms a Cycle