How to Reverse Words in a String?

  • 时间：2020-10-06 11:32:45
  • 分类：网络文摘
  • 阅读：139 次

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Input: “Let’s take LeetCode contest”
Output: “s’teL ekat edoCteeL tsetnoc”

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

Find Space and Reverse (C++)

We can walk through each character and find next space position or EOF. Then, we can reverse the substring and concatenate it to the result string.

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

class Solution {
public:
    string reverseWords(string s) {
        int len = s.length();
        int i = 0, j = 0;
        string r = "";
        while (i < len) {
            while ((i < len) && s[i] != ' ') ++ i;
            if ((i == len) || (s[i] == ' ')) {
                r += reverse(s.substr(j, i - j));    
            }
            if (i < len) r += ' ';
            j = ++ i;
        }
        return r;
    }
    
    string reverse(string s) {
        string r = s;
        for (int i = 0; i < r.length() / 2; ++ i) {
            char t = r[r.length() - 1 - i];
            r[r.length() - 1 - i] = r[i];
            r[i] = t;
        }
        return r;
    }
};
class Solution {
public:
    string reverseWords(string s) {
        int len = s.length();
        int i = 0, j = 0;
        string r = "";
        while (i < len) {
            while ((i < len) && s[i] != ' ') ++ i;
            if ((i == len) || (s[i] == ' ')) {
                r += reverse(s.substr(j, i - j));    
            }
            if (i < len) r += ' ';
            j = ++ i;
        }
        return r;
    }
    
    string reverse(string s) {
        string r = s;
        for (int i = 0; i < r.length() / 2; ++ i) {
            char t = r[r.length() - 1 - i];
            r[r.length() - 1 - i] = r[i];
            r[i] = t;
        }
        return r;
    }
};

The string reverse above implementation is O(N) time, and the reverse-words take O(N^2) considering the string concatenation in C++ is inefficient. Thus the overall complexity is O(N^3).

The C++ does not have a inbuilt split string method, however, you can use third party library such as boost.

The C++ std::reverse() takes two parameters: start and end iterator, then reverse it. So the above can be simplified without re-inventing the wheel:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    string reverseWords(string s) {
        int i = 0, len = s.size();
        while (i < len) {
            int j = i;
            while ((j < len) && (s[j] != ' ')) j ++;
            std::reverse(begin(s) + i, begin(s) + j);
            i = j + 1;
        }
        return s;
    }
};
class Solution {
public:
    string reverseWords(string s) {
        int i = 0, len = s.size();
        while (i < len) {
            int j = i;
            while ((j < len) && (s[j] != ' ')) j ++;
            std::reverse(begin(s) + i, begin(s) + j);
            i = j + 1;
        }
        return s;
    }
};

Split and Reverse Algorithm in Java

In Java, we can split the string into an array of words, then we can concatenate the reversed substrings using String Builder, which is performant when the number of concatenation is big.

1
2
3
4
5
6
7
8
9
10

class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder r = new StringBuilder();
        for (String word: words) {
            r.append(new StringBuffer(word).reverse().toString() + " ");
        }
        return r.toString().trim();
    }
}
class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder r = new StringBuilder();
        for (String word: words) {
            r.append(new StringBuffer(word).reverse().toString() + " ");
        }
        return r.toString().trim();
    }
}

Reverse Words in a String using Python

With Python, we can reverse a string easily using [::-1] syntax sugar. Thus, it is trivial to solve this in Python:

1
2
3
4
5
6

class Solution:
    def reverseWords(self, s: str) -> str:
        ans = []
        for w in s.split(' '):
            ans.append(w[::-1])
        return ' '.join(ans)
class Solution:
    def reverseWords(self, s: str) -> str:
        ans = []
        for w in s.split(' '):
            ans.append(w[::-1])
        return ' '.join(ans)

Using C++ istringstream

We can use the C++ istringstream to parse each token/words – and reverse them on the fly.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    string reverseWords(string s) {
        istringstream ss(s);
        string ans = "", str;
        while (ss >> str) {
            std::reverse(begin(str), end(str));
            ans += str + " ";
        }
        return ans.substr(0, ans.size() - 1);
    }
};
class Solution {
public:
    string reverseWords(string s) {
        istringstream ss(s);
        string ans = "", str;
        while (ss >> str) {
            std::reverse(begin(str), end(str));
            ans += str + " ";
        }
        return ans.substr(0, ans.size() - 1);
    }
};

Reversing string puzzles are often in interviews.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
华夏之声在线收听「听广播」　 香港之声在线收听「听广播」　 中国高速交通广播FM99.6在线收听「听广播」　 CRI环球资讯广播FM90.5在线收听「听广播」　 香港卫视直播-香港卫视在线直播观看「高清」　 翡翠台直播-TVB翡翠台在线直播「高清」　 凤凰卫视中文台在线直播「高清」　 凤凰卫视资讯台直播-凤凰资讯台在线直播「高清」　 星空卫视直播-星空卫视在线直播观看「高清」　 健康卫视直播-健康卫视在线直播观看「高清」　
评论列表
添加评论