680. Valid Palindrome II

Problem

Bài toán yêu cầu kiểm tra xem một chuỗi có thể trở thành palindrome (chuỗi đối xứng) sau khi xóa tối đa một ký tự hay không?

Approach

Sử dụng Two pointers

Dùng 2 pointer left and right để kiểm tra từ đầu và cuối chuỗi

Nếu ký tự tại s[left] và s[right] giống nhau, tiếp tục di chuyển con trỏ và trong left++, right—

Nếu ký tự tại s[left] và s[right] khác nhau, bạn cần kiểm tra việc bỏ đi một ký tự (bỏ s[left] hoặc bỏ s[right]) có tạo thành một chuỗi palindrome hay không

Hàm phụ kiểm tra palindrome

Viết một hàm phụ để kiểm tra xem một đoạn con của chuỗi có phải là palindrome hay không

Hàm này sẽ dùng lại kỹ thuật two pointer để kiểm tra nhanh

Trả về kết quả

Nếu việc xóa một ký tự (bỏ left hoặc bỏ right) tạo thành palindrome, return true

Nếu không, return false

Time and space complexity

Hàm phụ isPalindrome chạy trong O(n) với n là độ dài của chuỗi.

Trong trường hợp xấu nhất (khi gặp ký tự khác nhau), ta gọi hàm phụ tối đa 2 lần.

Tổng độ phức tạp là O(n).

SC: O(1)

Solution

typescripttypescript

1function validPalindrome(s: string): boolean {
2    function isPaindrome(str: string, left: number, right: number): boolean {
3	    while(left < right) {
4		    if(str[left] !== str[right]) {
5			    return false;
6		    }
7		    
8		    left++;
9		    right--
10	    }
11	    return true;
12    }
13    
14    let left = 0;
15    let right = s.length - 1;
16    
17    while(left < right) {
18	    if(s[left] !== s[right]) {
19		    return (
20			    isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1)
21		    )
22	    }
23	    left++;
24	    right--
25    }
26    
27    return true;
28};

Loading content...

680. Valid Palindrome II

Related Posts

Related Posts

680. Valid Palindrome II

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