最短独占单词缩写

/*
 * 题目思路：
 * 使用Java Stream API生成target的所有可能缩写，然后找到字典中不存在的最短缩写。
 */
 
import java.util.*;
import java.util.stream.*;
 
public class Solution {
    public String minAbbreviation(String target, String[] dictionary) {
        List<String> abbrs = generateAbbreviations(target).stream()
                .sorted(Comparator.comparingInt(String::length))
                .collect(Collectors.toList());
        return abbrs.stream()
                .filter(abbr -> !isConflict(abbr, dictionary))
                .findFirst()
                .orElse("");
    }
 
    private List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<>();
        generateAbbreviations(word, 0, new StringBuilder(), 0, result);
        return result;
    }
 
    private void generateAbbreviations(String word, int pos, StringBuilder cur, int count, List<String> result) {
        int len = cur.length();
        if (pos == word.length()) {
            if (count > 0) cur.append(count);
            result.add(cur.toString());
        } else {
            generateAbbreviations(word, pos + 1, cur, count + 1, result);
            if (count > 0) cur.append(count);
            cur.append(word.charAt(pos));
            generateAbbreviations(word, pos + 1, cur, 0, result);
        }
        cur.setLength(len);
    }
 
    private boolean isConflict(String abbr, String[] dictionary) {
        return Arrays.stream(dictionary).anyMatch(word -> match(word, abbr));
    }
 
    private boolean match(String word, String abbr) {
        int m = word.length(), n = abbr.length();
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (Character.isDigit(abbr.charAt(j))) {
                if (abbr.charAt(j) == '0') return false;
                int start = j;
                while (j < n && Character.isDigit(abbr.charAt(j))) j++;
                int num = Integer.parseInt(abbr.substring(start, j));
                i += num;
            } else {
                if (word.charAt(i++) != abbr.charAt(j++)) return false;
            }
        }
        return i == m && j == n;
    }
}