Java DP Solution


  • 0
    Y
    public class Solution {
        public List<String> generateAbbreviations(String word) {
            int m = word.length();
            List<Set<String>> dp = new ArrayList<Set<String>>();
            for (int i = 0; i <= m; i ++) dp.add(new HashSet<String>());
            dp.get(0).add("");
            for (int i = 1; i <= m; i ++) {
                Set<String> si = dp.get(i);
                for (int j = 0; j < i; j ++) {
                    for (String s : dp.get(j)) {
                        if (s.length() == 0 || !Character.isDigit(s.charAt(s.length() - 1)))
                            si.add(s + (i - j));
                        si.add(s + word.substring(j, i));
                    }
                }
            }
            return new ArrayList<String>(dp.get(word.length()));
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.