[LeetCode][680. Valid Palindrome II] 3 Approaches: Brute Force, Recursion and Two Pointers

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 3 分钟

By Long Luo

This article is the solution 3 Approaches: Brute Force, Recursion and Two Pointers of Problem 680. Valid Palindrome II.

Here shows 3 Approaches to slove this problem: Brue Force, Recursion and Two Pointers.

Brue Force

Let’s start from the simplest method:

  • if \(len(str) \le 2\), definitely return \(\textit{true}\);
  • if the string is a palindrome, return \(\textit{true}\);
  • if not, enumerate each position as the deleted position, and then check the remaining strings is it a palindrome.

Time complexity of this approach is \(O(n^2)\), time limit will be exceeded.

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
public static boolean validPalindrome_bf(String s) {
    int len = s.length();
    if (len <= 2 || validPalindrome(s, 0, len - 1)) {
        return true;
    }

    for (int i = 0; i < len; i++) {
        String str = s.substring(0, i) + s.substring(i + 1, len);
        if (validPalindrome(str, 0, str.length() - 1)) {
            return true;
        }
    }

    return false;
}

public static boolean validPalindrome(String s, int left, int right) {
    int len = s.length();
    if (left >= len || right < 0 || left > right) {
        return false;
    }

    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }

    return true;
}

Analysis

  • Time Complexity: \(O(n^2)\)
  • Space Complexity: \(O(1)\)

Recursion

Recursion solution is also easy, it is silimar to the two pointers approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Recursive time: O(n) space: O(1) TimeOut
public static boolean validPalindrome_recursive(String s) {
    return validPalindrome(s, 0, s.length() - 1, 1);
}

public static boolean validPalindrome(String s, int left, int right, int cnt) {
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            if (cnt > 0) {
                return validPalindrome(s, left + 1, right, cnt - 1) || validPalindrome(s, left, right - 1, cnt - 1);
            } else {
                return false;
            }
        }

        left++;
        right--;
    }

    return true;
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n / 2)\)

Two Pointers

An efficient way to check if a string is a palindrome is to use two pointers.

If the characters pointed to by the two pointers are different, one of the two characters must be deleted.

At this time, we can divide it into two cases:

  1. delete the character corresponding to the left pointer, leaving the substring \(s[low+1:high]\);
  2. delete the character corresponding to the right pointer, leaving the substring \(s[low:high−1]\).

When at least one of the two substrings is a palindrome, it means that the original string becomes a palindrome after deleting one character.

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
// Two Pointers time: O(n) space: O(1)
public static boolean validPalindrome_tp(String s) {
    int len = s.length();
    if (len <= 2) {
        return true;
    }

    int left = 0;
    int right = len - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return validPalindrome(s, left + 1, right) || validPalindrome(s, left, right - 1);
        } else {
            left++;
            right--;
        }
    }

    return true;
}

public static boolean validPalindrome(String s, int left, int right) {
    int len = s.length();
    if (left >= len || right < 0 || left > right) {
        return false;
    }

    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }

    return true;
}

Analysis

  • Time Complexity: \(O(n)\).
  • Space Complexity: \(O(1)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗