Java 8ms DFS solution, beats 100%!


  • 0
    R

    The key to reduce time is using char array to store path.


    public class Solution {
        public List<String> generateAbbreviations(String word) {
            // validate input
            if(word == null || word.length() == 0) {
                return Arrays.asList("");
            }
            
            // init
            int n = word.length();
            char[] workspace = new char[n];
            List<String> result = new ArrayList<>();
            
            // dfs
            dfs(word,0,n,0,workspace,result);
            
            // return
            return result;
        }
        
        private void dfs(String word, int offset, int n, int wpOffset, char[] workspace, List<String> result) {
            // base case
            if(offset == n) {
                result.add(new String(workspace,0,wpOffset));
                return;
            }
            
            // general case
            // dont abbreviate
            workspace[wpOffset] = word.charAt(offset);
            dfs(word,offset+1,n,wpOffset+1,workspace,result);
            
            // do abbreviate
            for(int i = offset; i < n; i++) {
                int length = i-offset+1;
                
                if(length < 10) {
                    workspace[wpOffset] = (char)(length+'0');
                    if(i+1 < n) {
                        workspace[wpOffset+1] = word.charAt(offset+length);
                        dfs(word,offset+length+1,n,wpOffset+2,workspace,result);
                    } else {
                        dfs(word,offset+length,n,wpOffset+1,workspace,result);
                    }
                } else {
                    String abbString = String.valueOf(length);
                    int abbLength = abbString.length();
                    
                    for(int j = 0; j < abbLength; j++) {
                        workspace[wpOffset+j] = abbString.charAt(j);
                    }
                    
                    if(i+1 < n) {
                        workspace[wpOffset+abbLength] = word.charAt(offset+length);
                        dfs(word,offset+length+1,n,wpOffset+abbLength+1,workspace,result);
                    } else {
                        dfs(word,offset+length,n,wpOffset+abbLength,workspace,result);
                    }
                }
            }
        }
    }

Log in to reply
 

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