Monday, December 8, 2014

LeetCode Reverse Words in a String

After splitting, there may be some " " string in the string array.
For example "a    b", the splitting result is "a", " ", "b".

public String reverseWords(String s) {
        if (s==null ||s.length()==0) return "";
   
    //split to words by space
    String[] arr = s.trim().split(" ");
    StringBuilder sb = new StringBuilder();
    for (int i=arr.length-1; i >=0; i--) {
       if (!"".equals(arr[i])) {
    sb.append(arr[i]).append(" ");
       }
    }
    return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
    }


Also there is a alternative solution for two passes and O(1) space.
The condition is there no spaces at the beginning and the tail. Every word is separated by single space.

Algorithm.
Reverse entire sentence.
Reverse every word.

No comments:

Post a Comment