How to Reverse Words in a String using Modern Programming Langua

  • 时间:2020-09-07 13:13:13
  • 分类:网络文摘
  • 阅读:107 次

Given an input string, reverse the string word by word.

Example 1:
Input: “the sky is blue”
Output: “blue is sky the”

Example 2:
Input: ” hello world! ”
Output: “world! hello”
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:
Input: “a good example”
Output: “example good a”
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

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) extra space.

Reverse Words using StringStream in C++

In C++, we don’t have easy ways to split a string. However, we can use stringstream to get next word and concatenate the string:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string reverseWords(string s) {
        stringstream all(s);
        string word = "", res = "";
        while (all >> word) {
            res = word + " " + res;
        }
        return res.substr(0, res.size() - 1);
    }
};
class Solution {
public:
    string reverseWords(string s) {
        stringstream all(s);
        string word = "", res = "";
        while (all >> word) {
            res = word + " " + res;
        }
        return res.substr(0, res.size() - 1);
    }
};

We can also reverse the entire string, then reverse each word, and finally concatenate them.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string reverseWords(string s) {          
        std::reverse(begin(s), end(s));
        stringstream all(s);
        string word = "", res = "";
        while (all >> word) {
            std::reverse(begin(word), end(word));
            res = res + " " + word;
        }
        return res.empty() ? "" : res.substr(1);
    }
};
class Solution {
public:
    string reverseWords(string s) {          
        std::reverse(begin(s), end(s));
        stringstream all(s);
        string word = "", res = "";
        while (all >> word) {
            std::reverse(begin(word), end(word));
            res = res + " " + word;
        }
        return res.empty() ? "" : res.substr(1);
    }
};

Using C++ stringstream to parse into words allows us to skip extra whitespaces. The first algorithm is more efficient than the second approach. The first implementation is O(N) time, and O(N) space if we consider string concatenation is O(1) constant runtime e.g. In Java/C#, we can use StringBuilder to achieve O(1) string concatenation.

The second approach has O(N^2) complexity, as we need to reverse each words in a string.

Using Filter in Java to Reverse the words

Java is verbose. We can split the string into array, then we need to use Arrays.stream to apply the filtering, then convert back to Array.

1
2
3
4
5
6
7
8
9
    
class Solution {
    public String reverseWords(String s) {
        var arr = s.split(" ");
        var list = Arrays.stream(arr).filter(x -> !x.isEmpty()).toArray(String[]::new);
        Collections.reverse(Arrays.asList(list));
        return String.join(" ", list);
    }
}
    
class Solution {
    public String reverseWords(String s) {
        var arr = s.split(" ");
        var list = Arrays.stream(arr).filter(x -> !x.isEmpty()).toArray(String[]::new);
        Collections.reverse(Arrays.asList(list));
        return String.join(" ", list);
    }
}

Next, we use Collections.reverse to reverse a List – which we also need to use Arrays.asList to convert an array in Java to List. Then, finally, we use String.join static method to concatenate the words in the array to string.

Using Javascript to Reverse words in a string

Javascript is Modern. We can do easy functional programming in Javascript. And it is fluent and easy.

1
2
3
4
5
6
7
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.trim().split(' ').reverse().filter(x => x.length > 0).join(' ');
};
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.trim().split(' ').reverse().filter(x => x.length > 0).join(' ');
};

Using Python’s Map/Reduce to reverse the words in a string

In Python, it is similar. We use filter (built-in function) that takes a lambda to filter out the empty whitespaces after spliting into words. As filtering returns a generator, we need to convert it to list, then we can reverse it.

1
2
3
4
5
class Solution:
    def reverseWords(self, s: str) -> str:
        arr = list(filter(lambda x: len(x) > 0, s.strip().split(' ')))
        arr.reverse()
        return ' '.join(arr)
class Solution:
    def reverseWords(self, s: str) -> str:
        arr = list(filter(lambda x: len(x) > 0, s.strip().split(' ')))
        arr.reverse()
        return ' '.join(arr)

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
如何添加和删除wordpress用户角色  如何使用 Velvet Blues Update URLs 插件更换wordpress站内链接  Gravatar头像无法加载的三种解决方案  为wordpress编辑器添加选择中文字体功能  让WordPress编辑器TinyMCE显示隐藏按钮  冬日趣事作文200字  走出来,真好  创新是不变的旋律  中华传统节日重阳节作文400字  怀揣感恩之心 
评论列表
添加评论