palindrome

public boolean (String s) {
    int begin = 0, end = s.length() - 1;
    while (begin < end) {
        while (begin < end && Character.isLetterOrDigit(s.charAt(begin)) == false)
            begin++;
        while (begin < end && Character.isLetterOrDigit(s.charAt(end)) == false)
            end--;
        char first = Character.toLowerCase(s.charAt(begin));
        char second = Character.toLowerCase(s.charAt(end));
        if (begin < end && first != second)
            return false;
        begin++;
        end--;
    }
    return true;
}

private String ans = "";
private int max = 0;
public void getString(String s, int left, int right) {
    while (left >= 0 && right < s.length()
            && s.charAt(left) == s.charAt(right)) {
        --left;
        ++right;
    }
    int len = right - 1 - left;
    if (len > max) {
        max = len;
        ans = s.substring(++left, right);
    }
}

public String longestPalindrome(String s) {
    if (s.length() == 0)
        return "";
    for (int i = 0; i < s.length(); ++i) {
        getString(s, i, i);
        getString(s, i, i + 1);
    }
    return ans;
}

public boolean (int x) {
    if (x < 0)
        return false;
    int head = 1;
    
    //     head *= 10;
    // } may overflow
    while (x / head >= 10)
        head *= 10;

    // while (x >= 10) {
    // 1000021
    while (x > 0) {
        int digit = x % 10;
        int first = x / head;
        if (digit != first)
            return false;
        x %= head;
        x /= 10;
        head /= 100;
    }
    return true;
}

public boolean (ListNode head) {
    if (head == null || head.next == null)
        return true;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode newNode = reverse(slow.next);
    slow.next = null;
    while (head != null && newNode != null) {
        if (head.val != newNode.val)
            return false;
        head = head.next;
        newNode = newNode.next;
    }
    return true;
}

public ListNode reverse(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode prev = null;
    while (head != null) {
        ListNode tmp = head.next;
        head.next = prev;
        prev = head;
        head = tmp;
    }
    return prev;
}

List<List<String>> ans = new ArrayList<List<String>>();
public List<List<String>> partition(String s) {
    if (s == null || s.length() == 0)
        return ans;
    boolean[][] valid = new boolean[s.length()][s.length()];
    for (int i = 0; i < s.length(); ++i)
        valid[i][i] = true;
    for (int i = 0; i < s.length() - 1; ++i) {
        if (s.charAt(i) == s.charAt(i + 1)) {
            valid[i][i + 1] = true;
        }
    }
    for (int len = 2; len < s.length(); ++len) {
        for (int i = 0; i < s.length() - len; ++i) {
            if (s.charAt(i) == s.charAt(i + len) && valid[i + 1][i + len - 1])
                valid[i][i + len] = true;
        }
    }
    List<String> path = new ArrayList<String>();
    dfs(s, 0, path, valid);
    return ans;
}

public void dfs(String s, int begin, List<String> path, boolean[][] valid) {
    if (begin == s.length()) {
        ans.add(new ArrayList<String>(path));
        return;
    }
    for (int i = begin; i < s.length(); ++i) {
        if (valid[begin][i] == false)
            continue;
        path.add(s.substring(begin, i + 1));
        dfs(s, i + 1, path, valid);
        path.remove(path.size() - 1);
    }
}

public int minCut(String s) {
    int n = s.length();
    boolean[][] valid = new boolean[n][n];
    for (int i = 0; i < s.length(); ++i)
        valid[i][i] = true;
    for (int i = 0; i < s.length() - 1; ++i) {
        if (s.charAt(i) == s.charAt(i + 1)) {
            valid[i][i + 1] = true;
        }
    }
    for (int len = 2; len < s.length(); ++len) {
        for (int i = 0; i < s.length() - len; ++i) {
            if (s.charAt(i) == s.charAt(i + len) && valid[i + 1][i + len - 1])
                valid[i][i + len] = true;
        }
    }
    int[] dp = new int[n];
    for (int i = 0; i < n; ++i) {
        dp[i] = i;
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (valid[j][i]) {
                if (j == 0)
                    dp[i] = 0;
                else
                    dp[i] = Math.min(dp[i], dp[j-1] + 1);
            }
        }
    }
    return dp[n - 1];
}

public boolean check(String s) {
        int begin = 0, end = s.length() - 1;
        while (begin <= end) {
            char c1 = s.charAt(begin), c2 = s.charAt(end);
            if (c1 != c2)
                return false;
            begin++; end--;
        }
        return true;
    }

    public String shortestPalindrome(String s) {
        if (s == null || s.length() <= 1)
            return s;
        String rev = new StringBuilder(s.substring(1)).reverse().toString();
        int min = Integer.MAX_VALUE;
        String ans = "";
        for (int i = rev.length(); i > 0; --i) {
            StringBuilder sb = new StringBuilder(s);
            String tmp = rev.substring(0, i);
            sb.insert(0, tmp);
            if (check(sb.toString()) && sb.length() < min) {
                min = sb.length();
                ans = sb.toString();
            }
        }
        return ans;
    }