LeetCode 125 - Valid Palindrome

https://leetcode.com/problems/valid-palindrome/

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

https://leetcode.com/problems/valid-palindrome/discuss/40029/Accepted-pretty-Java-solution(271ms)
https://leetcode.com/problems/valid-palindrome/discuss/40048/Here's-a-clean-C%2B%2B-solution

    public boolean isPalindrome(String s) {
        if (s.isEmpty()) {
         return true;
        }
        int head = 0, tail = s.length() - 1;
        char cHead, cTail;
        while(head <= tail) {
         cHead = s.charAt(head);
         cTail = s.charAt(tail);
         if (!Character.isLetterOrDigit(cHead)) {
          head++;
         } else if(!Character.isLetterOrDigit(cTail)) {
          tail--;
         } else {
          if (Character.toLowerCase(cHead) != Character.toLowerCase(cTail)) {
           return false;
          }
          head++;
          tail--;
         }
        }
        
        return true;
    }

X. https://leetcode.com/problems/valid-palindrome/discuss/39981/My-three-line-java-solution

    public boolean isPalindrome(String s) {
        String actual = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
        String rev = new StringBuffer(actual).reverse().toString();
        return actual.equals(rev);
    }

LeetCode 906 - Super Palindromes

https://leetcode.com/problems/super-palindromes/

Let's say a positive integer is a superpalindrome if it is a palindrome, and it is also the square of a palindrome.

Now, given two positive integers L and R (represented as strings), return the number of superpalindromes in the inclusive range [L, R].

Example 1:

Input: L = "4", R = "1000"
Output: 4
Explanation: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.

Note:

1. 1 <= len(L) <= 18
2. 1 <= len(R) <= 18
3. L and R are strings representing integers in the range [1, 10^18).
4. int(L) <= int(R)

http://hehejun.blogspot.com/2018/09/leetcodesuper-palindromes.html
这道题R的最大值可以到达10^18，所以我们只需要验证[1, 10^9]的回文，既然要求是回文，长度又可以砍一半，所以我们需要验证的是：

• [1, 9999]范围中的数为前一半，长度为偶数的回文
• [1, 99999]范围中的数为前一半，个位数为中心，长度为奇数的回文

因为10^9肯定不是回文，所以我们不需要管。这样可以保证我们遍历[1, 999999999]中的所有回文，我们依次check这些回文是不是满足要求。时间复杂度O(M^0.25 * log M)，M为R的最大值

https://leetcode.com/articles/super-palindromes/

• Time Complexity: $O(W^{\frac{1}{4}} * \log W)$∗logW), where $W = 10^{18}$ is our upper limit for $R$. The $\log W$ term comes from checking whether each candidate is the root of a palindrome.
• Space Complexity: $O(\log W)$, the space used to create the candidate palindrome. 

  public int superpalindromesInRange(String sL, String sR) {

    long L = Long.valueOf(sL);

    long R = Long.valueOf(sR);

    int MAGIC = 100000;

    int ans = 0;

    // count odd length;

    for (int k = 1; k < MAGIC; ++k) {

      StringBuilder sb = new StringBuilder(Integer.toString(k));

      for (int i = sb.length() - 2; i >= 0; --i)

        sb.append(sb.charAt(i));

      long v = Long.valueOf(sb.toString());

      v *= v;

      if (v > R)

        break;

      if (v >= L && isPalindrome(v))

        ans++;

    }

    // count even length;

    for (int k = 1; k < MAGIC; ++k) {

      StringBuilder sb = new StringBuilder(Integer.toString(k));

      for (int i = sb.length() - 1; i >= 0; --i)

        sb.append(sb.charAt(i));

      long v = Long.valueOf(sb.toString());

      v *= v;

      if (v > R)

        break;

      if (v >= L && isPalindrome(v))

        ans++;

    }

    return ans;

  }

  public boolean isPalindrome(long x) {

    return x == reverse(x);

  }

  public long reverse(long x) {

    long ans = 0;

    while (x > 0) {

      ans = 10 * ans + x % 10;

      x /= 10;

    }

    return ans;

  }

https://leetcode.com/problems/super-palindromes/discuss/170774/Java-building-the-next-palindrome

    public int superpalindromesInRange(String L, String R) {
        Long l = Long.valueOf(L), r = Long.valueOf(R);
        int result = 0;
        for (long i = (long)Math.sqrt(l); i * i <= r;) {
            long p = nextP(i);
            if (p * p <= r && isP(p * p)) {
                result++;
            }
            i = p + 1;
        }
        return result;
    }
    
    private long nextP(long l) {
        String s = "" + l;
        int len = s.length();
        List<Long> cands = new LinkedList<>();
        cands.add((long)Math.pow(10, len) - 1);
        String half = s.substring(0, (len + 1) / 2);
        String nextHalf = "" + (Long.valueOf(half) + 1);
        String reverse = new StringBuilder(half.substring(0, len / 2)).reverse().toString();
        String nextReverse = new StringBuilder(nextHalf.substring(0, len / 2)).reverse().toString();
        cands.add(Long.valueOf(half + reverse));
        cands.add(Long.valueOf(nextHalf + nextReverse));
        long result = Long.MAX_VALUE;
        for (long i : cands) {
            if (i >= l) {
                result = Math.min(result, i);
            }
        }
        return result;
    }
    
    private boolean isP(long l) {
        String s = "" + l;
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
        return true;
    }

X. Precompute
https://leetcode.com/problems/super-palindromes/discuss/170748/Just-Run-a-brute-force-locally-and-print-table!
Just Run a brute-force locally and print table!
https://leetcode.com/problems/super-palindromes/discuss/170728/no-more-this-type-questions-for-contest!

vector<uint64_t> value {
    0, 1, 4, 9, 121, 484, 676, 10201, 12321, 14641, 40804, 44944, 69696, 94249, 698896, 1002001, 1234321, 
    4008004, 5221225, 6948496, 100020001, 102030201, 104060401, 121242121, 123454321, 125686521, 400080004, 
    404090404, 522808225, 617323716, 942060249, 10000200001, 10221412201, 12102420121, 12345654321, 
    40000800004, 637832238736, 1000002000001, 1002003002001, 1004006004001, 1020304030201, 1022325232201, 
    1024348434201, 1086078706801, 1210024200121, 1212225222121, 1214428244121, 1230127210321, 1232346432321, 
    1234567654321, 1615108015161, 4000008000004, 4004009004004, 4051154511504, 5265533355625, 9420645460249, 
    100000020000001, 100220141022001, 102012040210201, 102234363432201, 121000242000121, 121242363242121, 
    123212464212321, 123456787654321, 123862676268321, 144678292876441, 165551171155561, 400000080000004, 
    900075181570009, 4099923883299904, 10000000200000001, 10002000300020001, 10004000600040001, 10020210401202001, 
    10022212521222001, 10024214841242001, 10201020402010201, 10203040504030201, 10205060806050201, 
    10221432623412201, 10223454745432201, 12100002420000121, 12102202520220121, 12104402820440121, 
    12120030703002121, 12122232623222121, 12124434743442121, 12321024642012321, 12323244744232321, 
    12341234943214321, 12343456865434321, 12345678987654321, 40000000800000004, 40004000900040004, 94206450305460249,
};

class Solution {
public:
    int superpalindromesInRange(string L, string R) {
        auto l = lower_bound(value.begin(), value.end(), stoull(L));
        auto r = upper_bound(value.begin(), value.end(), stoull(R));
        int res = 0;
        for (;l != r; ++l) {
            int64_t v = *l;
            int64_t root = round(sqrt(v));
            string s1 = to_string(root);
            string s2 = s1;
            reverse(s2.begin(), s2.end());
            if (s2 == s1) ++res;
        }
        return res;
    }




LeetCode 680 - Valid Palindrome II

https://leetcode.com/problems/valid-palindrome-ii/description/

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

https://www.cnblogs.com/grandyang/p/7618468.html
这道题是之前那道Valid Palindrome的拓展，还是让我们验证回复字符串，但是区别是这道题的字符串中只含有小写字母，而且这道题允许删除一个字符，那么当遇到不匹配的时候，我们到底是删除左边的字符，还是右边的字符呢，我们的做法是两种情况都要算一遍，只要有一种能返回true，那么结果就返回true。我们可以写一个子函数来判断字符串中的某一个范围内的子字符串是否为回文串

X. Greedy

If the beginning and end characters of a string are the same (ie. s[0] == s[s.length - 1]), then whether the inner characters are a palindrome (s[1], s[2], ..., s[s.length - 2]) uniquely determines whether the entire string is a palindrome.

Algorithm

Suppose we want to know whether s[i], s[i+1], ..., s[j] form a palindrome. If i >= j then we are done. If s[i] == s[j] then we may take i++; j--. Otherwise, the palindrome must be either s[i+1], s[i+2], ..., s[j] or s[i], s[i+1], ..., s[j-1], and we should check both cases.

    public boolean isPalindromeRange(String s, int i, int j) {

        for (int k = i; k <= i + (j - i) / 2; k++) {

            if (s.charAt(k) != s.charAt(j - k + i)) return false;

        }

        return true;

    }

    public boolean validPalindrome(String s) {

        for (int i = 0; i < s.length() / 2; i++) {

            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {

                int j = s.length() - 1 - i;

                return (isPalindromeRange(s, i+1, j) ||

                        isPalindromeRange(s, i, j-1));

            }

        }

        return true;

    }

public boolean validPalindrome(String s) {

char[] chs = s.toCharArray();

// BUG: ArrayIndexOutOfBoundsException not chs.length

Result result = checkValidPalindrome(chs, 0, chs.length - 1);

// case ab

// aba abba case

if (result.valid)

return true;

// a[i]!=a[j]

// abca

int i = result.start;

int j = result.end;

return checkValidPalindrome(chs, i + 1, j).valid || checkValidPalindrome(chs, i, j - 1).valid;

}

// aba

// precondition: start > 0 && end < chs.length - 1

public Result checkValidPalindrome(char[] chs, int start, int end) {

while (start < end) {

if (chs[start] == chs[end]) {

start++;

end--;

} else {

break;

}

}

return new Result(start, end, start >= end);

}

private static class Result {

private int start, end;

private boolean valid;

public Result(int start, int end, boolean valid) {

super();

this.start = start;

this.end = end;

this.valid = valid;

}

}

Check from left and right at the same time until the first different pair.
Now we have something like a****b, where a and b are different.
We need to delete either a or b to make it a palindrome
https://leetcode.com/problems/valid-palindrome-ii/discuss/107714/Java-solution-isPalindrome

Follow normal way (two pointers) to check if s is palindrome. When two chars are not equal, try to skip (pseudo delete) either left one or right one and continue checking.

    public boolean validPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j && s.charAt(i) == s.charAt(j)) {
            i++; j--;
        }

        if (i >= j) return true;

        if (isPalin(s, i + 1, j) || isPalin(s, i, j - 1)) return true;
        return false;
    }

    private boolean isPalin(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) == s.charAt(j)) {
                i++; j--;
            }
            else return false;
        }
        return true;
    }

https://leetcode.com/problems/valid-palindrome-ii/discuss/107716/Java-O(n)-Time-O(1)-Space

public boolean validPalindrome(String s) {
    int l = -1, r = s.length();
    while (++l < --r) 
        if (s.charAt(l) != s.charAt(r)) return isPalindromic(s, l, r+1) || isPalindromic(s, l-1, r);
    return true;
}

public boolean isPalindromic(String s, int l, int r) {
    while (++l < --r) 
        if (s.charAt(l) != s.charAt(r)) return false;
    return true;
}

X.
https://leetcode.com/articles/valid-palindrome-ii/
Approach #1: Brute Force [Time Limit Exceeded]
For each index i in the given string, let's remove that character, then check if the resulting string is a palindrome. If it is, (or if the original string was a palindrome), then we'll return true

Time Complexity: $O(N^2)$ where $N$ is the length of the string. We do the following $N$ times: create a string of length $N$ and iterate over it.

  public boolean isPalindrome(CharSequence s) {

    for (int i = 0; i < s.length() / 2; i++) {

      if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {

        return false;

      }

    }

    return true;

  }

  public boolean validPalindrome(String s) {

    StringBuilder sb = new StringBuilder(s);

    for (int i = 0; i < s.length(); i++) {

      char c = sb.charAt(i);

      sb.deleteCharAt(i);

      if (isPalindrome(sb))

        return true;

      sb.insert(i, c);

    }

    return isPalindrome(s);

  }