A DP Java Solution


  • 0
    O
        public class Solution {
            public List<String> generateAbbreviations(String word) {
                int len = word.length();
                List<String>[] letterHead = new List[len + 1]; 
                List<String>[] digitHead = new List[len + 1];
                for (int i = 0; i <= len; letterHead[i] = new ArrayList(), digitHead[i] = new ArrayList(), i++);
                
                letterHead[len].add(""); // DP boundary
                digitHead[len].add(""); 
                if (len < 1) return letterHead[0];
                letterHead[len - 1].add(word.substring(len - 1)); 
                digitHead[len - 1].add("1");
                
                for (int i = len - 2; i >= 0; i--) {
                    String s = word.substring(i, i + 1);
                    for (String sub : letterHead[i + 1]) letterHead[i].add(s + sub);
                    for (String sub : digitHead[i + 1]) letterHead[i].add(s + sub);
                    
                    for (int j = 1; i + j <= len; j++) {
                        s = String.valueOf(j);
                        for (String sub : letterHead[i + j]) digitHead[i].add(s + sub);
                    }
                }
                
                for (String sub : digitHead[0]) letterHead[0].add(sub); 
                // now letterHead is not pure letter-head now
                
                return letterHead[0];
            }
        }
    
    38ms

Log in to reply
 

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