Is my solution good enough?


  • 16
    B

    Following is my accepted solution. However I found it quite long and not concise. Can someone help me improving my code?

    void reverseStr(string &s, int start, int end)
        {
            int i = start;
            int j = end;
            while(i<j)
            {
                swap(s[i],s[j]);
                i++;
                j--;
            }
        }
        void reverseStr(string &s)
        {
            reverseStr(s, 0, s.size()-1);
        }
        void reverseWords(string &s) {
            //reverse entire
            reverseStr(s);
            //reverse each word
            int start = 0;
            int end = 0;
            int i = 0;
            //remove leading space
            while(s.size() >0 && s[0] == ' ')
            {
                s.erase(0,1);
            }
            //add one space to the end so that it is easy to read word
            s += ' ';
            for(int i = 0; i < s.size(); ++i)
            {
                if(s[i] != ' ')
                    end++;
                //remove multiple space
                while(s[i] == ' ' && i < s.size()-1 && s[i+1] == ' ')
                {
                    s.erase(i,1);
                }
                //reverse word
                if(s[i] == ' ')
                {
                    if(end>start)
                    {
                        reverseStr(s, start, end-1);
                        start = end + 1;
                        end = start;
                    }
                }
            }
            //remove last ' '
            s.erase(s.size()-1, 1);
            
            
        }

  • 18
    K

    I think maybe it is better to conside using extra space O(n), which will make codes more concise and run faster.
    Because when we remove extra space in a string, it may take O(n) time.
    Here is my solution.
    Mine time complexity is O(n) and space complexity is O(n) too:

    	void reverseWords(string &s)
    {
    	string rs;
    	for (int i = s.length()-1; i >= 0; )
    	{
    		while (i >= 0 && s[i] == ' ') i--;
    		if (i < 0) break;
    		if (!rs.empty()) rs.push_back(' ');
    		string t;
    		while (i >= 0 && s[i] != ' ') t.push_back(s[i--]);
    		reverse(t.begin(), t.end());
    		rs.append(t);
    	}
    	s = rs;
    }
    

  • 5
    S

    I'm using python.

    1. strip the leading and trailing spaces
    2. split with white space as separator
    3. reverse the resulting list
    4. join them with white space

    done

    class Solution:
    # @param s, a string
    # @return a string
    def reverseWords(self, s):
        t = s.strip().rsplit()
        t.reverse()
        return " ".join(t)

  • 0
    B

    This really makes me want to learn Python! It looks like there are a lot more built in functions in Python, I am not sure if it is fine to use them in an interview?


  • 0
    S

    I believe it won't work for a real interview. :S


  • 0
    B

    good idea! I guess I was trying too hard to use constant space. This seems to be a better solution.


  • 1
    W

    Java solution, space O(n), time O(n)

    public String reverseWords(String s) {
        ArrayList<String> buf = new ArrayList<String>();
        s += ' ';
        int n = s.length(), h = -1;
        for(int i=0; i<n; i++) {
            if(h == -1 && s.charAt(i) != ' ')   h = i;
            else if(h != -1 && s.charAt(i) == ' ') {
                buf.add(0,s.substring(h,i));
                h = -1;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(String iter : buf)  sb.append(iter+" ");
        return sb.length() == 0 ? "" : sb.substring(0,sb.length()-1).toString();
    }

  • 7
    H

    Im using Java, with O(n) time and O(n) space. I can improve by manually splitting the string and use stringBuffer here, but the core idea is it is really easy to use a stack here. Because of the reverse logic.

    public class Solution {
        public String reverseWords(String s) {
            
            Stack<String> stack = new Stack<String>();
            String tokens[] = s.split(" ");
            int length = tokens.length;
            String reverseStr = "";
            
            for(int i = 0 ; i < length; i ++){
                
               if(tokens[i].equals(""))
                    continue;
               // System.out.println(tokens[i] + "sssssssss");
                stack.push(tokens[i]);
            }
            
            while(!stack.isEmpty()){
                
                String temp = stack.pop();
                if(reverseStr == ""){
                    reverseStr = reverseStr.concat(temp);
                }else{
                    reverseStr = reverseStr.concat(" ");
                    reverseStr = reverseStr.concat(temp);
                }
            }
            
            return reverseStr;
        }
    }

  • 3
    C

    Here is a Java solution using a stack.

      public static String reverseWords(String s){
    	String[] str=s.split(" ");
    	Stack<String> stack=new Stack<String>();
    	StringBuilder buff=new StringBuilder();
    	for(String iter:str) {
    		if(!iter.equals("")) stack.push(iter);}
    	while(!stack.isEmpty())
    	{buff.append(stack.pop()); 
    	if(!stack.isEmpty()) buff.append(" ");}
    	return buff.toString();
    }

  • 0
    F
    public static String reverseWords(String s){
    	String reverseWord = "";
    	int len = s.length();
    	if (len == 0) return "";
    	StringBuffer sb = new StringBuffer();
    	String temp = "";
    	boolean first = true;
    	boolean isSpace = false;
    	for (int i = len-1;i>=0;i--){
    		if (s.charAt(i) == ' ' && sb.length() != 0){
    			//if (!isSpace) reverseWord +=" ";
    			if (first)
    				{
    				sb.reverse();
    				first = false;
    				}
    			else sb.append(' ').reverse();				
    			reverseWord += sb.toString();
    			isSpace = true;
    			sb = new StringBuffer();
    			continue;
    		}
    		else if (s.charAt(i) != ' '){
    			isSpace = false;
    			sb.append(s.charAt(i));
    		}			
    	}
    	if (reverseWord.length()>1 && sb.length()>0)
    	 reverseWord += sb.append(' ').reverse().toString();
    	else if (sb.length()>0 && reverseWord.length()<1)
    		return sb.reverse().toString();
    	else return reverseWord;
    	return reverseWord;
    }
    

    I use String Buffer however, I have to deal with many annoying special cases, which make me freak out


  • 1
    E

    Just post a solution of myself in Java. Seems the answer is long for me too.

    public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        
        char[] chars = s.toCharArray();
        
        //Step1: Reverse the whole string
        int length = chars.length;
        reverse(chars, 0, length);
        
        //Step2: remove unnecessary spaces
        int lastIndex = removeExtraSpaces(chars);
        
        //Step3: reverse word by word
        reverseWordByWord(chars, lastIndex); 
        
        return new String(chars, 0, lastIndex + 1);
    }
    
    public void reverseWordByWord(char[] chars, int lastIndex) {
    	int wordStart = 0;
        for (int i = 0; i <= lastIndex; i++) {
            if (chars[i] == ' ') {
            	reverse(chars, wordStart, i);
            	wordStart = i + 1;
            } else if (i == lastIndex){
            	reverse(chars, wordStart, lastIndex + 1);
            }
        }
    }
    
    public int removeExtraSpaces(char[] chars) {
    	int a = -1;
        boolean spaceAllowed = false;
        int length = chars.length;
        for (int i = 0; i < length; i++) {
            if (chars[i] == ' ') {
                if (spaceAllowed && (i + 1 < length) && chars[i+1] != ' ') {
                    chars[++a] = chars[i];
                    spaceAllowed = false;
                }
                continue;
            }
            chars[++a] = chars[i];
            spaceAllowed = true;
        }
        return a;
    }
    
    public void reverse(char[] chars, int a, int b) {
    	if (a >= b) return;
    	for (int j = a; j <= a + (b - 1 - a) / 2; j++) {
        	swap(chars, j, a + b - 1 - j);
        }
    }
    
    public void swap(char[] chars, int x, int y) {
    	char c = chars[x];
    	chars[x] = chars[y];
    	chars[y] = c;
    }
    

    }


  • 0
    B

    substring actually is very time consuming. Better not use it.


  • 0
    J

    Anyone know if it is acceptable to use .split in an interview?


  • 0
    T

    but the author's code is very neat, which is good


  • 0
    I

    Here is a simple accepted python code for this problem.
    The idea here is keep 2 pointers pointed to the start of a word and end of a word, assume they are front and end, respectively. Also allocate a pointer to an empty string for later string concatenation.
    Then we increment end to the right by 1 at a time, then determine the 4 combinations of s[end] and s[end+1]

    1. If end is not len(s)-1

      1.1. If s[end] is space and s[end+1] is space: no word, do nothing

      1.2. If s[end] is space and s[end+1] is not space: got a start of a new word, move front to end+1

      1.3. if s[end] is not space and s[end+1] is space: got an end of a word, add this word to the result string in the front

      1.4. If s[end] is not space and s[end+1] is not space: in the middle of a word, do nothing

    2. If end is len(s) - 1, which means we are in the last position, and because we have already trimmed the string, the last char is guaranteed not space, so we just add the substring to result string

       def reverseWords(self, s):
       if s is None:
           return None
       if len(s) == 0:
           return s
       s = s.strip()       # get rid of leading and trailing spaces
       front = 0
       space = ' '
       r = ''
       for end in xrange(len(s)):
           if end != len(s) - 1:
               if s[end] == space and s[end+1] == space:
                   continue
               if s[end] == space and s[end+1] != space:
                   front = end + 1
               if s[end] != space and s[end+1] == space:
                   r = s[front:end+1] + r
                   front = end + 1
                   r = space + r
               if s[end] != space and s[end+1] != space:
                   continue
           else:
               r = s[front:end+1] + r
       return r
      

    I did not make the code concise (which it can be done) just that I can understand the code later myself...


  • 0
    W

    My suggestion is that you don't bother with white spaces. Just reverse the string using your strategy.
    Then deal with the spaces in one run. You just need two pointers or indexes.
    The time complexity is still O(n) and space complexity is O(1).

    In an interview, this quesiton normally requires O(1) space.


  • 0
    W

    Constant space usage is the essence of this problem. You will be definitely asked about it.


  • 0

    elegant code..thanks!


  • 0
    S

    elegant indeed, thanks!


  • 0
    N

    thats crazy.


Log in to reply
 

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