Java solution with O(1) space


  • 0
    M

    Parsing through the whole string only once. O(1) extra space.

    public class Solution {
        public String reverseWords(String s) {
            if(s==null){
                return null;
            }
            if(s.length()==0){
                return "";
            }
            StringBuilder sb=new StringBuilder();
            int pos=0;
            for(int i=0; i<s.length();i++){
                if(s.charAt(i)==' '){
                    pos=0;
                    continue;
                }
                if(pos==0){
                    sb.insert(pos,' ');
                    pos++;
                }
                sb.insert(pos,s.charAt(i));
                pos++;
            }
        return sb.toString().trim();
        }
    }
    

    Update: insert function takes linear time. So reducing the number of times i call insert. This solution seems to run faster than the previous one. But, it uses one more stringbuilder variable, so extra space.

    public class Solution {
        public String reverseWords(String s) {
            if(s==null){
                return null;
            }
            if(s.length()==0){
                return "";
            }
            StringBuilder sb=new StringBuilder();
            StringBuilder word=new StringBuilder();
            int pos=0,end=0;
            for(int i=0; i<s.length();i++){
                if(s.charAt(i)==' '){
                    word.insert(0,sb.toString());
                    sb.setLength(0);
                    pos=0;
                    continue;
                }
                if(pos==0){
                    sb.append(' ');
                    pos++;
                }
                sb.append(s.charAt(i));
                
            }
        word.insert(0,sb.toString());    
        return word.toString().trim();
        }
    }
    

Log in to reply
 

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