首页 > itarticle > 151. reverse words in a string 实现

151. reverse words in a string 实现

admin 11月 14, 2020 0

Given an input string, reverse the string word by word.
Example:
Input: “the sky is blue”,
Output: “blue is sky the”.
Note:
A word is defined as a sequence of non-space characters.
Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
You need to reduce multiple spaces between two words to a single space in the reversed string.
Follow up: For C programmers, try to solve it in-place in O(1) space.

给的字符串,根据单词来翻转.其中不能有连续的空格,如果有保留一个,前后空格不能存在.

实现

  • java

利用正则表达式将前后空格删除,根据正则两多个空格删除,保留一个空格.

1
2
3
4
5
6
7
8
9
10
 
public static String (String s) {
      StringBuilder builder = new StringBuilder(s.trim().replaceAll("r|n|\s+"," "));
      String[] arys = builder.toString().split(" ");
      StringBuilder b = new StringBuilder();
      int length = arys.length;
      for (int i=length-1;i>=0;i--){
          b.append(arys[i]).append(" ");
      }
      return b.toString().trim();
    }

  • go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
package leetcode

import (
	"strings"
	"fmt"
)

func Reverse(s string) string {
   str := strings.TrimSpace(s)
   strAry := strings.Split(str," ")
   fmt.Println(strAry)
   size := len(strAry) - 1
   res := ""
   for i:=size ;i >= 0 ; i-- {
   	if len(strAry[i])> 0{
		res += strAry[i]
		if i!=0 {
			res += " "
		}
	}
   }
   return res
}

讨论区其他答案

  • go
1
2
3
4
5
6
7
8
9
10
 
func (s string) string {
	fields := strings.Fields(s)

	var reverses []string
	for i := len(fields)-1; i >= 0; i-- {
		reverses = append(reverses, fields[i])
	}

	return strings.Join(reverses, " ")
}
  • java

java两个指针来解决问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
public class Solution {
  
  public String (String s) {
    if (s == null) return null;
    
    char[] a = s.toCharArray();
    int n = a.length;
    
    
    reverse(a, 0, n - 1);
    // step 2. reverse each word
    reverseWords(a, n);
    // step 3. clean up spaces
    return cleanSpaces(a, n);
  }
  
  void (char[] a, int n) {
    int i = 0, j = 0;
      
    while (i < n) {
      while (i < j || i < n && a[i] == ' ') i++; // skip spaces
      while (j < i || j < n && a[j] != ' ') j++; // skip non spaces
      reverse(a, i, j - 1);                      // reverse the word
    }
  }
  
  // trim leading, trailing and multiple spaces
  String cleanSpaces(char[] a, int n) {
    int i = 0, j = 0;
      
    while (j < n) {
      while (j < n && a[j] == ' ') j++;             // skip spaces
      while (j < n && a[j] != ' ') a[i++] = a[j++]; // keep non spaces
      while (j < n && a[j] == ' ') j++;             // skip spaces
      if (j < n) a[i++] = ' ';                      // keep only one space
    }
  
    return new String(a).substring(0, i);
  }
  
  // reverse a[] from a[i] to a[j]
  private void reverse(char[] a, int i, int j) {
    while (i < j) {
      char t = a[i];
      a[i++] = a[j];
      a[j--] = t;
    }
  }
  
}
  • CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void (string &s) {
    reverse(s.begin(), s.end());
    int storeIndex = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] != ' ') {
            if (storeIndex != 0) s[storeIndex++] = ' ';
            int j = i;
            while (j < s.size() && s[j] != ' ') { s[storeIndex++] = s[j++]; }
            reverse(s.begin() + storeIndex - (j - i), s.begin() + storeIndex);
            i = j;
        }
    }
    s.erase(s.begin() + storeIndex, s.end());
}

参考

如有错误,欢迎批评指正,望不吝赐教!!!

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能