Google – Compress String II

Google – Compress String II
假设一个文件压缩后的表示是:
#3, #5, #6, 2 5, #8
#d表示单个数字d
两个数字"i j"表示取前i个数字，组长度为j的字符串。
比如 "#3" 就表示3
"2 5"表示前面两个数字，就是56，组成长度为5的字符串，就是56565
所以上面的例子，解压缩之后应该是: 3 5 6 5 6 5 6 5 8
要求是写一个压缩算法，把string按要求压缩。
比如 2 3 4 5 2 3 4 5 1, 返回#2, #3, #4, #5, 4 4, #1
[Solution]
一边扫描一边用hashtable 记录window size为2的pattern, map到这个Pattern所有出现过的位置，如果发现重复的，就开始往后match。
面经上写着window size为3，并且map到最后出现的位置，应该是不对。首先window size为3就不知道是为什么。其次map到最后出现的位置也有问题，比如
3 5 6 1 4 5 6 1 5 5 6 1 4 5 6 1 5
第二个5 6 1后面是5，并不能match第一个5 6 1后面的4。要直到第三个5 6 1才能match前面8个字符。但是如果5 6 1map到最后出现的位置的话，是无法继续match下去的。

  public String compress(String s) {

    if (s == null || s.isEmpty()) {

      return s;

    }

 

    Map<String, List<Integer>> map = new HashMap<>();

    StringBuilder sb = new StringBuilder();

    sb.append("#" + s.charAt(0));

    for (int i = 1; i < s.length(); i++) {

      String pattern = String.format("%c%c", s.charAt(i - 1), s.charAt(i));

      if (!map.containsKey(pattern)) {

        map.put(pattern, new ArrayList<>());

        sb.append(" ").append("#" + s.charAt(i));

      }

      else {

        boolean found = false;

        for (int j : map.get(pattern)) {

          int l = j + 1;

          int r = i + 1;

          while (r < s.length() && s.charAt(l) == s.charAt(r)) {

            l++;

            r++;

          }

          if (l < i - 1) {

            continue;

          }

          else {

            int prevNum = i - j;

            int len = r - i + 1;

            sb.delete(sb.length() - 3, sb.length());

            sb.append(" ").append(prevNum + " " + len);

            found = true;

            i = r - 1;

            break;

          }

        }

        if (!found) {

          sb.append(" ").append("#" + s.charAt(i));

        }

      }

 

      map.get(pattern).add(i);

    }

 

    return sb.toString();

  }

Read full article from Google – Compress String II