public class Solution {
    /**
     * @param word: the given word
     * @return: the generalized abbreviations of a word
     */
    public List<String> generateAbbreviations(String word) {

        // Write your code here



        Set<String> set = helper(word);


        return new ArrayList<>(set);
    }

    Map<String, Set<String>> memo = new HashMap<>();

    //'ab'
    private Set<String> helper(String w) {

        if (memo.get(w) != null) {
            return memo.get(w);
        }

        Set<String> ans = new HashSet<>();

        if (w.length() == 1) {
            ans.add(w);
            ans.add("1");
            return ans;
        }

        // 'abcd' => 'a' 'bcd' => 'a' 'b' 'cd'
        // 'abcd' => 'ab' 'cd' => 'a' 'b' 'cd'

        // i include in first part
        for (int i = 0;  i < w.length() - 1; i++) {

            // 'a' '1'
            Set<String> firstPart = helper(w.substring(0, i+1));
            // 'b' '1'
            Set<String> secondPart = helper(w.substring(i+1, w.length()));


            for (String first : firstPart) {
                for (String second :secondPart) {


                    Integer firstBack = getBackDigit(first);
                    Integer secondFront = getFrontDigit(second);

                    if (firstBack != null && secondFront != null) {
                        //  a10
                        //  10b

                        ans.add(
                            first.substring(0, first.length() - String.valueOf(firstBack).length()) +  //'a'
                            (firstBack + secondFront) +  // 20
                            second.substring(String.valueOf(secondFront).length(), second.length()) // 'b'
                        );

                    } else {
                        // 'a' 1
                        // 'a' 'b'
                        // 1 'b'

                        ans.add((first + second));
                    }
                }
            }
        }

        memo.put(w, ans);

        return ans;
    }

    boolean isDigit(char c) {
        return c >= '0' && c <= '9';
    }

    Integer getFrontDigit(String s) {

        if (!isDigit(s.charAt(0))) {
            return null;
        }

        int curr = 0;

        int i = 0;
        while (i < s.length() && isDigit(s.charAt(i))) {
            curr = curr * 10;
            curr += s.charAt(i) - '0';
            i++;
        }

        return curr;
    }

    Integer getBackDigit(String s) {
        if (!isDigit(s.charAt(s.length() - 1))) {
            return null;
        }

        int k = 1;
        int curr = 0;

        int i = s.length() - 1;
        while (i >=0 && isDigit(s.charAt(i))) {
            curr += (s.charAt(i) - '0') * k;
            i--;
            k = k * 10;
        }
        return curr;
    }
}