Leetcode 678. Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Example 1:

Input: "()"
Output: True

Example 2:

Input: "(*)"
Output: True

Example 3:

Input: "(*))"
Output: True

Note:

1. The string size will be in the range [1, 100].

Intuition

When checking whether the string is valid, we only cared about the "balance": the number of extra, open left brackets as we parsed through the string. For example, when checking whether '(()())' is valid, we had a balance of 1, 2, 1, 2, 1, 0 as we parse through the string: '(' has 1 left bracket, '((' has 2, '(()' has 1, and so on. This means that after parsing the first i symbols, (which may include asterisks,) we only need to keep track of what the balance could be.

For example, if we have string '(***)', then as we parse each symbol, the set of possible values for the balance is [1] for '('; [0, 1, 2] for '(*'; [0, 1, 2, 3] for '(**'; [0, 1, 2, 3, 4] for '(***', and [0, 1, 2, 3] for '(***)'.

Furthermore, we can prove these states always form a contiguous interval. Thus, we only need to know the left and right bounds of this interval. That is, we would keep those intermediate states described above as [lo, hi] = [1, 1], [0, 2], [0, 3], [0, 4], [0, 3].

Algorithm

Let lo, hi respectively be the smallest and largest possible number of open left brackets after processing the current character in the string.

If we encounter a left bracket (c == '('), then lo++, otherwise we could write a right bracket, so lo--. If we encounter what can be a left bracket (c != ')'), then hi++, otherwise we must write a right bracket, so hi--. If hi < 0, then the current prefix can't be made valid no matter what our choices are. Also, we can never have less than 0 open left brackets. At the end, we should check that we can have exactly 0 open left brackets.

Code (Java):

class Solution {
    public boolean checkValidString(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int lo = 0;
        int hi = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') {
                lo++;
                hi++;
            } else if (c == ')') {
                if (lo > 0) {
                    lo--;
                }
                hi--;
            } else {
                if (lo > 0) {
                    lo--;
                }
                hi++;
            }

            if (hi < 0) {
                return false;
            }
        }

        return lo == 0;
    }
}

Leetcode 616. Add Bold Tag in String

Given a string s and a list of strings dict, you need to add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

Example 1:

Input: 
s = "abcxyz123"
dict = ["abc","123"]
Output:
"<b>abc</b>xyz<b>123</b>"

Example 2:

Input: 
s = "aaabbcc"
dict = ["aaa","aab","bc"]
Output:
"<b>aaabbc</b>c"

Note:

1. The given dict won't contain duplicates, and its length won't exceed 100.
2. All the strings in input have length in range [1, 1000].

Code (Java):

class Solution {
    public String addBoldTag(String s, String[] dict) {
        if (dict == null || dict.length == 0) {
            return s;
        }

        // step 1: find start and end pos of the substring
        //
        List<Interval> intervals = new ArrayList<>();
        for (String t : dict) {
            strStr(s, t, intervals);
        }
        
        if (intervals.isEmpty()) {
            return s;
        }

        // step 2: sort the intervals based on the start index
        //
        Collections.sort(intervals, new IntervalComparator());

        // step 3: merge intervals
        //
        List<Interval> mergedIntervals = mergeIntervals(intervals);

        // step 4: compose the result based on the merged intervals
        //
        StringBuilder sb = new StringBuilder();
        int prev = 0;
        
        for (int i = 0; i < mergedIntervals.size(); i++) {
            Interval curr = mergedIntervals.get(i);
            // prev seg
            //
            sb.append(s.substring(prev, curr.start));
            sb.append("<b>");
            
            // curr seg
            //
            sb.append(s.substring(curr.start, curr.end + 1));
            sb.append("</b>");
            
            prev = curr.end + 1;
        }
        
        // trailing substring
        //
        if (prev < s.length()) {
            sb.append(s.substring(prev));
        }

        return sb.toString();
    }

    private void strStr(String s, String t, List<Interval> list) {
        for (int i = 0; i < s.length() - t.length() + 1; i++) {
            int j = 0;
            while (j < t.length()) {
                if (s.charAt(i + j) == t.charAt(j)) {
                    j++;
                } else {
                    break;
                }
            }

            if (j == t.length()) {
                Interval interval = new Interval(i, i + j - 1);
                list.add(interval);
            }
        }
    }

    private List<Interval> mergeIntervals(List<Interval> intervals) {
        List<Interval> ans = new ArrayList<>();
        
        if (intervals == null || intervals.isEmpty()) {
            return ans;
        }

        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (prev.end >= curr.start || prev.end + 1 == curr.start) {
                prev.end = Math.max(prev.end, curr.end);
            } else {
                ans.add(new Interval(prev.start, prev.end));
                prev = curr;
            }
        }

        ans.add(prev);

        return ans;
    }
}

class Interval {
        int start;
        int end;

        public Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

class IntervalComparator implements Comparator<Interval> {
    public int compare(Interval a, Interval b) {
        return a.start - b.start;
    }
}

Leetcode 680. Valid Palindrome II

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.

Code (Java):

class Solution {
    public boolean validPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return true;
        }
        
        int left = 0;
        int right = s.length() - 1;
        
        while  ( left < right && s.charAt(left) == s.charAt(right)) {
            left++;
            right--;
        }
        
        if (left >= right) {
            return true;
        }
            
        if (isPalin(s, left + 1, right) || 
            isPalin(s, left, right - 1)) {
                return true;
        }
        
        return false;
    }
    
    private boolean isPalin(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                break;
            }
        }
        
        return left >= right;
    }
}

Leetcode 606. Construct String from Binary Tree

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     

Output: "1(2(4))(3)"

Explanation: Originallay it needs to be "1(2(4)())(3()())", 
but you need to omit all the unnecessary empty parenthesis pairs. 
And it will be "1(2(4))(3)".

Example 2:

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 

Output: "1(2()(4))(3)"

Explanation: Almost the same as the first example, 
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public String tree2str(TreeNode t) {
        if (t == null) {
            return "";
        }

        String leftChild = tree2str(t.left);
        String rightChild = tree2str(t.right);

        if (leftChild.isEmpty() && rightChild.isEmpty()) {
            return t.val + "";
        }
        
        String r = (rightChild.isEmpty() ? "" : "(" + rightChild + ")");

        return t.val + "(" + leftChild + ")" + r;
    }
}

Leetcode 583. Delete Operation for Two Strings

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

Example 1:

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Note:

1. The length of given words won't exceed 500.
2. Characters in given words can only be lower-case letters.

Code (Java):

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 1; i <= word2.length(); i++) {
            dp[0][i] = i;
        }

        for (int j = 1; j <= word1.length(); j++) {
            dp[j][0] = j;
        }

        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        return dp[word1.length()][word2.length()];
    }
}

Leetcode 557. Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

Code (Java):

class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        int start = 0;
        int end = 0;

        char[] arr = s.toCharArray();

        while (end < s.length()) {
            while (end < s.length() && s.charAt(end) != ' ') {
                end++;
            }
            reverse(arr, start, end - 1);
            end++;
            start = end;
        }

        reverse(arr, start, end - 1);

        return new String(arr);
    }

    private void reverse(char[] arr, int start, int end) {
        while (start < end) {
            char temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
}

Leetcode 556. Next Greater Element III

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer nand is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

Example 1:

Input: 12
Output: 21

Example 2:

Input: 21
Output: -1

Code (Java):

class Solution {
    public int nextGreaterElement(int n) {
        String s = n + "";
        char[] arr = s.toCharArray();

        // step 1: go from end and find the descreasing number
        //
        int i = s.length() - 2;
        while (i >= 0 && s.charAt(i) >= s.charAt(i + 1)) {
            i--;
        }

        if (i < 0) {
            return -1;
        }

        int j = i + 1;
        while (j < s.length() && s.charAt(j) > s.charAt(i)) {
            j++;
        }
        j--;

        swap(arr, i, j);

        reverse(arr, i + 1);

        String ans = new String(arr);
        
        Long l = Long.parseLong(ans);
        if (l >= Integer.MAX_VALUE) {
            return -1;
        }

        return Integer.parseInt(ans);
    }

    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

    }

    private void reverse(char[] arr, int start) {
        int end = arr.length - 1;

        while (start < end) {
            swap(arr, start, end);
            start++;
            end--;
        }
    }
}

Leetcode 551. Student Attendance Record I

You are given a string representing an attendance record for a student. The record only contains the following three characters:

1. 'A' : Absent.
2. 'L' : Late.
3. 'P' : Present.

A student could be rewarded if his attendance record doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:

Input: "PPALLP"
Output: True

Example 2:

Input: "PPALLL"
Output: False

Code (Java):

class Solution {
    public boolean checkRecord(String s) {
        if (s == null || s.length() < 2) {
            return true;
        }

        int cLate = 0;
        int cAbsent = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == 'A') {
                cAbsent++;
            } else if (c == 'L') {
                cLate = 0;
                // check the number of contiguous lates
                //
                while (i < s.length() && s.charAt(i) == 'L') {
                    cLate++;
                    i++;
                }
                i--;
            }

            if (cAbsent > 1 || cLate > 2) {
                return false;
            }
        }

        return true;
    }
}