Java - A Simple Idea


  • 0
    C

    This method came into my mind when I just saw the problem. The constraint is that '1' cannot be the part of the word.

    Let's take "word" as an example. We start from "word" itself. And at each time, we flip one character to '1', and translate it to abbreviation.

    Level 1: word -> 1ord, w1rd, wo1d, wor1
    Level 2:

    • 1ord -> 11rd, 1o1d, 1or1
    • w1rd -> w11d, w1r1
    • wo1d -> wo11
    • wor1 -> nothing

    Level 3:

    • 11rd -> 111d, 11r1
    • 1o1d -> 1o11
    • 1or1 -> nothing
    • w11d -> ... etc

    Note that this problem is similar to integer decomposition or finding all subsets for a set.

    Here is the code.

    public class Solution {
        public List<String> generateAbbreviations(String word) {
            List<String> result = new ArrayList<>();
            if(word.length() == 0){
                result.add(word);
                return result;
            }
            
            Queue<String> queue = new LinkedList<>();
            queue.add(word);
            int len = word.length();
            
            while(!queue.isEmpty()){
                String s = queue.poll();
                StringBuffer sb = new StringBuffer(s);
                int idx = s.lastIndexOf('1');
                
                result.add(getAbb(s));
                
                for(int i = idx + 1; i < len; i++){
                    char c = s.charAt(i);
                    sb.setCharAt(i, '1');
                    queue.add(sb.toString());
                    sb.setCharAt(i, c);
                }
                
            }
            
            return result;
        }
        
        private String getAbb(String s){
            char[] sArray = s.toCharArray();
            int count = 0;
            StringBuilder sb= new StringBuilder();
            
            for(char c : sArray){
                if(c == '1') count++;
                else{
                    if(count != 0) sb.append(count);
                    count = 0;
                    sb.append(c);
                }
            }
            
            if(sArray[s.length() - 1] == '1') sb.append(count);
            
            return sb.toString();
        }
    }

Log in to reply
 

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