Accepted Solution in Java, few API used


  • 0
    W
    public class Solution {
        public String reverseWords(String s) {
            
            if(s == null)return null;
            if(s.length() == 0)return s;
            if(s.length() == 1){
                if(s.charAt(0) == ' ')return "";
                else return s;
            }
            
            int h=0,t=0,p=0,top=0,pos=0, size=s.length();
            char[] stack = new char[size+1];
            char[] result;
            
            do{
                // skip all the whitespaces
                while(h<size && s.charAt(h)==' ')h++;       // be careful of outOfBoundException
                // reached first letter, set tail to head
                t=h;
                // move tail to the end of the word
                while(t<size && s.charAt(t)!=' ')t++;       // be careful of outOfBoundException
                // reached the end of the word, push reversed word to stack
                
                // ==== how to handle "    "? ====
                
                // break if the string is all whitespace
                if(h == size && t == size)break;
                
                for(p=t-1; p>=h; p--){
                    stack[top++] = s.charAt(p);
                }
                // put a white space after the reversed word
                stack[top++] = ' ';
                
                // move head to the first whitespace after the word and continue to process next word
                h=t;
                
            }while(h<size);
            
            if(top == 0)return "";
            
            // now pop the stack to form the result string
            // eht_yks_si_eulb_
            top=top-2; // skip the last whitespace
            result = new char[top+1]; // now instantiate result array with final length
            
            while(top>=0){
                result[pos++] = stack[top--];
            }
            
            return new String(result);
            
        }
    }

  • 0
    W

    Can be easily improved.

    Go through the string and just push the index of the beginning and end of each word into a stack. Then pop the index to get the words in reversed order.

    eg. " the sky is blue ", stack: [2,4,7,9,12,13,15,18]
    15, 18 -> blue; 12, 13 -> is; 7, 9 -> sky; 2, 4 -> the
    result: [blue, is, sky, the]


  • 2
    K

    it can be simpler:

    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        String[] split = s.split("\\s+");
        int len = split.length;
        for(int i=len-1; i>=0; i--){
            sb.append(split[i]).append(" ");
        }
        return sb.toString().trim();
    }
    

  • 0
    W

    Thanks dude, it is true. I just want to implement without APIs like split(), StringBuilder, and trim().


Log in to reply
 

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