LeetCode 320. Generalized Abbreviation

LC address: https://leetcode.com/problems/generalized-abbreviation/

Write a function to generate the generalized abbreviations of a word.

Example:

Given word = "word", return the following list (order does not matter):

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Analysis:

这道题还挺有意思的，乍一看很简单，但是实现的时候感觉还是需要思考的，可能是我个人对于String类型的各种题目不太熟悉吧。

这题有两种解法，首先想到的是bottom-up的方法，就是把一个长单词打散，通过小单元的结合再合成长单词，类似于mergesort，但是这个方法很不高效，需要反复处理string，代码也颇为复杂（至少我是这么觉得的）。另一种就比较简单了，利用dfs的搜索方式从头到尾遍历，每一个char可以有两种选择，变成数字或者保留原型，代码很清晰易懂，O(n^2)的复杂度。

Solution:

solution 1: Bottom-Up 188ms

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> abbrevList = new ArrayList<>();
        if (word.length() == 0) {
            abbrevList.add("");
        } else if (word.length() == 1) {
            abbrevList.add(word);
            abbrevList.add("1");
        } else {
            String lastPattern = "[0-9]+$";
            String firstPattern = "^[0-9]+";
            String left = word.substring(0, word.length() / 2);
            String right = word.substring(word.length() / 2, word.length());
            List<String> leftList = generateAbbreviations(left);
            List<String> rightList = generateAbbreviations(right);
            for (String l : leftList) {
                for (String r : rightList) {
                    String ls = l.replaceAll(lastPattern, "");
                    String rs = r.replaceAll(firstPattern, "");
                    if (ls.length() != l.length() && rs.length() != r.length()) {
                        int ln = Integer.parseInt(l.substring(ls.length()));
                        int rn = Integer.parseInt(r.substring(0, r.length() - rs.length()));
                        int i = ln + rn;
                        abbrevList.add(ls + i + rs);
                    } else {
                        abbrevList.add(l + r);
                    }
                }
            }
        }
        return abbrevList;
    }
}

solution 2: DFS 19ms

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> abbrevList = new ArrayList<>();
        if (word.length() == 0) {
            abbrevList.add("");
        } else {
            String curString = "";
            int start = 0;
            int end = word.length();
            int count = 0;
            dfs(curString, start, end, count, abbrevList, word);
        }
        return abbrevList;
    }
    
    private void dfs(String curString, int start, int end,
        int count, List<String> abbrevList, String original) {
        if (start < end) {
            dfs(curString, start + 1, end, count + 1, abbrevList, original);
            String newString = "";
            if (count > 0) {
                newString += count;
                count = 0;
            }
            newString = curString + newString + original.charAt(start);
            dfs(newString, start + 1, end, count, abbrevList, original);
        } else {
            if (count > 0) {
                curString += count;
            }
            abbrevList.add(curString);
        }
    }
}

Solution code can also be found here: https://github.com/all4win/LeetCode.git