2016年7月14日星期四

[LintCode] #53 Reverse Words in a String

* reverse each word, and then reverse the entire string
sky_is_blue => yks_si_eulb => blue_is_sky

public class Solution {
    /**
     * @param s : A string
     * @return : A string
     */
    public String reverseWords(String s) {
       if (s == null || s.length() == 0) {
           return s;
       }
       
       String[] A = s.split(" ");
       if (A.length == 0 ) {
           return "";
       }
       
       StringBuilder sb = new StringBuilder();
       for (int i = A.length - 1; i >= 0; i--) {
           sb.append(A[i]);
           if (i != 0) {
               sb.append(" ");
           }
       }
       
       return new String(sb);
    }
}

* This one not working, because of it can't remove redundant spaces

public class Solution {
    public String reverseWords(String s) {
       char[] tmp = s.toCharArray();
       int start = 0;
       while(start < tmp.length) {
           while (start < tmp.length && tmp[start] == ' ') {
               start++;
           }
           if (start >= tmp.length) {
               break;
           }
           
           int end = start;
           while (end < tmp.length && tmp[end] != ' ') {
               end++;
           }
           if (start < tmp.length && end <= tmp.length) {
               reverse(start, end - 1, tmp);
           }
           
           start = end;
       }
       reverse(0, tmp.length - 1, tmp);
       return new String(tmp);
    }
    
    private void reverse(int start, int end, char[] A) {
        while (start < end) {
            char tmp = A[start];
            A[start] = A[end];
            A[end] = tmp;
            
            start++;
            end--;
        }
    }
}

没有评论:

发表评论