151. Reverse Words in a String

Problem

Bài toán yêu cầu đảo ngược thứ tự các từ trong một chuỗi, đảm bảo:

Không có khoảng trắng thừa ở đầu, cuối hoặc giữa các từ (Chỉ duy nhất 1 dấu cách giữa các từ)

Các từ được xác định là chuỗi ký tự không phải dấu cách

Approach - Built in function

Loại bỏ các khoảng trắng thừa ở đầu và cuối chuỗi

Tách chuỗi thành mảng các từ, sử dụng biểu thức chính quy để xử lý nhiều dấu cách liên tiếp

Đảo ngược mảng các từ

Ghép lại thành chuỗi, mỗi từ cách nhau đúng 1 dấu cách

Time and space complexity

TC: O(n)

SC: O(n)

Solution

typescripttypescript

1function reverseWords(s: string): string {
2    const trim = s.trim();
3    const words = trim.split(/\s+/);
4    words.reverse()
5    return words.join(' ');
6};

Approach - Not use built in function

Duyệt chuỗi từ phải sang trái để lấy từng từ (vì đảo ngược thứ tự từ)

Bỏ qua các dấu cách thừa (ở đầu, cuối, giữa các từ)

Lưu từng từ vào một mảng kết quả

Ghép các từ lại với đúng 1 dấu cách giữa các từ

Solution

typescripttypescript

1function reverseWords(s: string): string {
2    const n = s.length;
3    let res = '';
4    let i = n -1;
5    while(i >= 0) {
6	    while(i >= 0 && s[i] === ' ') i--;
7	    if (i < 0) break;
8	    let end = i;
9	    
10	    while (i >= 0 && s[i] !== ' ') i--;
11	    let start = i + 1;
12	    if(res.length > 0) res += ' ';
13	    for(let j = start; j <= end; j++) {
14		    res += s[j]
15	    }
16    }
17    
18    return res;
19};

💡

Tóm tắt

Duyệt từ cuối chuỗi về đầu đề lấy từng từ theo thứ tự đảo ngược

Bỏ qua các dấu cách thừa bằng while(i >= 0 && s[i]===' ')

Xác định vị trí đầu và cuối của từng từ rồi nối vào kết quả

Chỉ nối đâu cách khi cần (nếu kết quả đã có từ trước đó)

Loading content...

151. Reverse Words in a String

Related Posts

Related Posts

151. Reverse Words in a String

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists