1/29 parse 和数学表达式计算
Regular Expression Matching
This Solution use 2D DP. very simple.
Here are some conditions to figure out, then the logic can be very straightforward.
1, If p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*':
here are two sub conditions:
1 if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //in this case, a* only counts as empty
2 if p.charAt(j-1) == s.charAt(i) or p.charAt(j-1) == '.':
dp[i][j] = dp[i-1][j] //in this case, a* counts as multiple a
or dp[i][j] = dp[i][j-1] // in this case, a* counts as single a
or dp[i][j] = dp[i][j-2] // in this case, a* counts as empty
the code is the following,
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
// corner case and initialization
dp[0][0] = true; // just think about the condition, s="", p=""
for (int i = 0; i < p.length(); i++) { // think about the condition s="" p="5*"
if (p.charAt(i) == '*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
// parse based on different conditions
for (int i = 0 ; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.') {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
dp[i+1][j+1] = dp[i+1][j-1];
} else {
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
}
}
}
}
return dp[s.length()][p.length()];
}
Wildcard Matching
The most confusing part for me is how to deal with '*'. At first I couldn't figure out why the condition would be (dp[i-1][j] == true || dp[i][j-1] == true). Hope detailed DP description below helps!
dp[i][j]: true if the first i char in String s matches the first j chars in String p
Base case:
- origin: dp[0][0]: they do match, so dp[0][0] = true
- first row: dp[0][j]: except for String p starts with *, otherwise all false
- first col: dp[i][0]: can't match when p is empty. All false.
Recursion:
- Iterate through every dp[i][j]
- dp[i][j] = true:
- if (s[ith] == p[jth] || p[jth] == '?') && dp[i-1][j-1] == true
elif p[jth] == '*' && (dp[i-1][j] == true || dp[i][j-1] == true)
-for dp\[i - 1\]\[j\], means that \* acts like any sequence. eg. abcd, ab\* -for dp\[i\]\[j - 1\], means that \* acts like an empty sequence. e.g ab, ab\*
-for dp[i-1][j], means that * acts like an empty sequence. eg: ab, ab*
Start from 0 to len
Output put should be dp[s.len][p.len], referring to the whole s matches the whole p
Be careful about the difference of index i,j in String (0 to len-1) and the index i, j in dp (0 to len)!
class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) return false;
int sLen = s.length();
int pLen = p.length();
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
// base case
dp[0][0] = true;
for (int i = 1; i <= sLen; i++) {
dp[i][0] = false;
}
for (int j = 1; j <= pLen; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// Recursion
for(int i = 1; i <= sLen; i++){
for(int j = 1; j <= pLen; j++){
if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?')
dp[i][j] = dp[i - 1][j - 1];
else if (p.charAt(j-1) == '*')
dp[i][j] = dp[i-1][j] || dp[i][j-1];
}
}
return dp[sLen][pLen];
}
}
Simplify Path
we can use one stack to solve this problem. And for each string in the array, we need to analyze it, and determine whether we need to pop or push one element.
public String simplifyPath(String path) {
String[] dir = path.split("/");
Deque<String> stack = new LinkedList<>();
Set<String> set = new HashSet<>(Arrays.asList(".", "..", ""));
for (String str : dir) {
if (str.equals("..") && !stack.isEmpty()) stack.pop();
else if (!set.contains(str)) stack.push(str);
}
String ans = "";
while (!stack.isEmpty()) {
ans = "/" + stack.pop() + ans;
}
return (ans == "") ? "/" : ans;
}
Longest Common Prefix
take the first string as base, and compare corresponding character with other string. If the index exceeds the length of the string or they are not equal, we just return the substring.
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
StringBuilder sb = new StringBuilder();
String str = strs[0]; // get the first string
for (int i = 0; i < str.length(); ++i) {
for (String s : strs) {
if (i >= s.length() || s.charAt(i) != str.charAt(i)) return str.substring(0, i);
}
}
return str;
}
}
Add Binary
代码简洁的重点在于处理“终止条件”，因为两个string很可能长度不一，也有可能两个string加完了之后还有进位没有处理。
class Solution {
public String addBinary(String a, String b) {
StringBuilder sum = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry != 0) {
int digitA = i < 0 ? 0 : a.charAt(i--) - '0';
int digitB = j < 0 ? 0 : b.charAt(j--) - '0';
sum.append((digitA + digitB + carry) % 2);
carry = (digitA + digitB + carry) / 2;
}
return sum.reverse().toString();
}
}
related problems: add two numbers, add strings
Multiply Strings
好题，好好掌握！首先给出一个straightforward的做法，就是先分解为两个基本操作，一个是multiplyOne()即一个数字乘以一个字符串，和addTwo()即两个字符串相加。
class Solution {
public String multiply(String num1, String num2) {
String longStr = (num1.length() > num2.length()) ? num1 : num2;
String shortStr = (num1.length() > num2.length()) ? num2 : num1;
String rst = "";
int index = 0;
while (shortStr.length() - 1 - index >= 0) {
int num = shortStr.charAt(shortStr.length() - 1 - index) - '0';
String cur = multiplyOne(longStr, num);
for (int i = index; i > 0; --i) {
cur += '0';
}
rst = addTwo(rst, cur);
index++;
}
return rst;
}
private String multiplyOne(String src, int num) {
if (num == 0) return "0";
StringBuilder sb = new StringBuilder();
int carry = 0;
for (int i = src.length() - 1; i >= 0; --i) {
int digit = src.charAt(i) - '0';
sb.append((digit * num + carry) % 10);
carry = (digit * num + carry) / 10;
}
if (carry > 0) sb.append(carry);
return sb.reverse().toString();
}
private String addTwo(String num1, String num2) {
StringBuilder sb = new StringBuilder();
int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry != 0) {
int val1 = i < 0 ? 0 : num1.charAt(i--) - '0';
int val2 = j < 0 ? 0 : num2.charAt(j--) - '0';
sb.append((val1 + val2 + carry) % 10);
carry = (val1 + val2 + carry) / 10;
}
return sb.reverse().toString();
}
}
上一种做法不够高效，如何improve。更简洁的方法是，
Start from right to left, perform multiplication on every pair of digits, and add them together. Based on below graph, we can conclude two facts:
- if string a with length of m multiplied by string b with length of n, the length of the product will not exceed m + n.
- num1[i] * num2[j]` will be placed at indices `[i + j`, `i + j + 1]
so we can define a Integer array to store the intermediate result, which would be changed multiple times. The basic idea is the one digit multiplication. But beyond that, we need to consider old value in the Integer array. For example,...
class Solution {
public String multiply(String num1, String num2) {
if (num1 == null || num2 == null) return null;
int maxLength = num1.length() + num2.length();
int[] nums = new int[maxLength];
int i, j, product, carry;
for (i = num1.length() - 1; i >= 0; --i) {
carry = 0;
for (j = num2.length() - 1; j >= 0; --j) {
int a = num1.charAt(i) - '0';
int b = num2.charAt(j) - '0';
product = nums[i + j + 1] + a * b + carry;
nums[i + j + 1] = product % 10;
carry = product / 10;
}
nums[i + j + 1] = carry;
}
StringBuilder sb = new StringBuilder();
for(int p : nums) if (!(sb.length() == 0 && p == 0)) sb.append(p);
return sb.length() == 0 ? "0" : sb.toString();
}
}
Longest Valid Parentheses
similar to remove invalid parentheses, can check it in String DFS.
For problems like valid parentheses, we can use stack to store '(' for validation. Since we are interested in length in this problem, we can store index in the stack. Initially, we push -1 into stack. For every '(' we encounter, we push its index onto stack. For every ')' we encounter, we first pop out its paired ')' from stack and subtract the index on the top of the stack to get the valid length. But if the stack becomes empty after we pop out the top element, we should push the current elements index onto the stack. In this way, we keep on calculating the length of the valid substrings, and return the length of the longest valid substring.
Time:O(N)
Space:O(N)
class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) return 0;
int maxLen = 0;
Deque<Integer> stack = new LinkedList<>(); // store the index before the starting point of a valid substring
stack.push(-1); // initialize
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (c == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
maxLen = Math.max(maxLen, i - stack.peek());
}
}
}
return maxLen;
}
}
solution 2: two scans
we make use of two counters left and right. We start traversing the string from left towards right. For every '(', increment left and for every ')', increment right. When right == left, we calculate the valid substring length and update max length; when right > left, we reset left and right to be 0.
Then we scan from right to left and applied the same procedure. [why scan again? For example: '((()']
Time: O(N) Space: O(1)
class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) return 0;
int n = s.length();
int maxLen = 0;
int left = 0, right = 0;
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) { // find a valid substring
maxLen = Math.max(maxLen, left + right);
} else if (right > left) {
left = right = 0; // invalid, reset left and right
}
}
left = right = 0;
// scan from right to left
for (int i = n - 1; i >= 0; --i) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxLen = Math.max(maxLen, left + right);
} else if (left > right) {
left = right = 0;
}
}
return maxLen;
}
}
solution 3: DP
The idea is go through the string and use DP to store the longest valid parentheses at that point. When we encounter ')', there are two situations:
- ()(), dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
- ..()(()), dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
class Solution {
public int longestValidParentheses(String s) {
int maxans = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ?dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
}
}
Different Ways to Add Parentheses
为了避免dfs + backtracking可能遇到的overlap subproblem返回多个结果的 问题，可以先直接divide & conquer，因为这个搜索结构是树状的，天生的disjoint. 根据这个思想，我们可以以“操作符”为分隔，借鉴编译器和reverse polish notation中的"expression tree"来进行计算. 问题的关键，如何想到或者如何构建divide & conquer 结构。外面需要一个for loop，里面递归得到left 和right的List<Integer>，然后再并列两个for loop，交叉配对。
class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> rst = new ArrayList<>();
for (int i = 0; i < input.length(); ++i) {
if (!Character.isDigit(input.charAt(i))) {
char operator = input.charAt(i);
List<Integer> left = diffWaysToCompute(input.substring(0, i));
List<Integer> right = diffWaysToCompute(input.substring(i + 1));
for (int num1 : left) {
for (int num2 : right) {
if (operator == '+') rst.add(num1 + num2);
if (operator == '-') rst.add(num1 - num2);
if (operator == '*') rst.add(num1 * num2);
}
}
}
}
if (rst.size() == 0) rst.add(Integer.parseInt(input));
return rst;
}
}
带记忆化搜索的方法更加的高效：
class Solution {
public List<Integer> diffWaysToCompute(String input) {
return helper(input, new HashMap<String, List<Integer>());
}
public List<Integer> helper(String input, Map<String, List<Integer>> map) {
if(map.containsKey(input)) return map.get(input);
List<Integer> rst = new ArrayList<>();
for (int i = 0; i < input.length(); ++i) {
if (!Character.isDigit(input.charAt(i))) {
char operator = input.charAt(i);
List<Integer> left = helper(input.substring(0, i));
List<Integer> right = helper(input.substring(i + 1));
for (int num1 : left) {
for (int num2 : right) {
if (operator == '+') rst.add(num1 + num2);
if (operator == '-') rst.add(num1 - num2);
if (operator == '*') rst.add(num1 * num2);
}
}
}
}
if (rst.size() == 0) rst.add(Integer.parseInt(input));
map.put(input, rst);
return rst;
}
}
Fraction Addition and Subtraction
Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should beirreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator
1.So in this case,2should be converted to2/1.
note: 有两个点需要好好注意，一个是如何分解string，还有个就是如何计算gcd(greatest common divisor)
- 掌握用Euclidean algorithm to compute GCD, https://en.wikipedia.org/wiki/Euclidean_algorithm
public int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
- 如何巧妙运用regex expression. https://www.geeksforgeeks.org/write-regular-expressions/ https://www.regular-expressions.info/index.html In this problem, expression.split("(+)|(-)"), 意思是用"+" or "-" 作为分隔符来分割string。
public class Solution {
public String fractionAddition(String expression) {
List < Character > sign = new ArrayList < > ();
if (expression.charAt(0) != '-')
sign.add('+');
for (int i = 0; i < expression.length(); i++) {
if (expression.charAt(i) == '+' || expression.charAt(i) == '-')
sign.add(expression.charAt(i));
}
int prev_num = 0, prev_den = 1, i = 0;
for (String sub: expression.split("(\\+)|(-)")) {
if (sub.length() > 0) {
String[] fraction = sub.split("/");
int num = (Integer.parseInt(fraction[0]));
int den = (Integer.parseInt(fraction[1]));
if (sign.get(i++) == '+')
prev_num = prev_num * den + num * prev_den;
else
prev_num = prev_num * den - num * prev_den;
prev_den = den * prev_den;
int g = Math.abs(gcd(prev_den, prev_num));
prev_num /= g;
prev_den /= g;
}
}
return prev_num + "/" + prev_den;
}
public int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
}
calculator problems
related problems: Evaluate Reverse Polish Notation, Expression Add Operators
naive calculator
only have +, -, non-negative integers and spaces.
class Solution {
public int calculate(String s) {
// we can just use a variable to record the last operator we met
if (s == null || s.length() == 0) return 0;
char last = '+';
int prev = 0;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (c == ' ') {
continue;
}
else if (Character.isDigit(c)) {
int num = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
i++;
}
i--;
if (last == '+') {
prev = prev + num;
} else {
prev = prev - num;
}
}
else {
last = c;
}
}
return prev;
}
}
basic calculator 1
only have +,-,(), non-negative integers and spaces.
the key is that we can use a stack to store the global sign and a variable to record the local sign. When we meet the '(', we just convert the local sign to global sign and put it to the stack, and update local sign as 1. When we meet the ')', we just implement the stack.pop() once.
class Solution {
public int calculate(String s) {
// we can just use a variable to record the last operator we met
if (s == null || s.length() == 0) return 0;
Deque<Integer> stack = new LinkedList<>();
stack.push(1);
int sum = 0;
int localSign = 1;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (c == ' ') {
continue;
}
else if (Character.isDigit(c)) {
int num = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
i++;
}
i--;
sum += num * localSign * stack.peek();
}
else if (c == '+') {
localSign = 1;
}
else if (c == '-') {
localSign = -1;
}
else if (c == '(') {
stack.push(localSign * stack.peek()); // record the global sign at this position.
localSign = 1;
}
else if (c == ')') {
stack.pop(); // pop out the global sign at this level
}
}
return sum;
}
}
basic calculator 2
only have +,-,*,/, non-negative integers and spaces.
像这种只有两个优先级的calculator，可以直接用stack来做，存储优先级较低的，遇到高优先级就处理。这道题，用stack存储 prev operator 为 + 或 - 的num，然后当遇到*或/的时候从stack去数字进行计算。
class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) return 0;
Deque<Integer> stack = new LinkedList<>();
char prev = '+';
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
if (ch == ' ') continue;
if (Character.isDigit(ch)) {
int num = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
num = num * 10 + s.charAt(i) - '0';
i++;
}
i--;
if (prev == '+') {
stack.push(num);
} else if (prev == '-') {
stack.push(-num);
} else if (prev == '*') {
int left = stack.pop();
stack.push(left * num);
} else if (prev == '/') {
int left = stack.pop();
stack.push(left / num);
}
} else { // ch is + - * /
prev = ch;
}
}
int ans = 0;
while (!stack.isEmpty()) {
ans += stack.pop();
}
return ans;
}
}
basic calculator 3
have +,-,*,/, (, ), non-negative integers and spaces.
如果优先级等级数>= 2, 我们就要用two stack + Sharding algorithm to solve the problems.
in the first step, use Sharding algorithm to convert original expression into the RPN expression. rpn stack to store the RPN expression, op stack to store the operators,
rpn stack ------------------ original expression \| op stackin the second step, use stack to solve the RPN expression. use stack to store the number involved.
import java.math.BigInteger;
class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) return 0;
String rpn = getRPN(s);
return solveRPN(rpn);
}
private String getRPN(String s) {
StringBuilder sb = new StringBuilder();
Deque<Character> stack = new LinkedList<>();
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (c == ' ') continue;
if (Character.isDigit(c)) {
sb.append(c);
continue;
}
// used for spliting the string
sb.append(" ");
if (c == '(') {
stack.push(c);
} else if (c == ')') {
// search for the '(' until we meet the ')'
while (stack.peek() != '(') {
sb.append(stack.pop());
sb.append(" ");
}
stack.pop(); // pop up the '('
} else if ("+-*/".indexOf(c) != -1) {
// put all the operators with high priority into the stringbuilder
while (!stack.isEmpty() && stack.peek() != '('
&& getPriority(c) <= getPriority(stack.peek())) {
sb.append(stack.pop());
sb.append(" ");
}
stack.push(c);
}
}
// finally put remaining operators in the stack into the stringBuilder
while (!stack.isEmpty()) {
sb.append(" ");
sb.append(stack.pop());
}
return sb.toString();
}
private int getPriority(char c) {
if (c == '+' || c == '-') return 0;
if (c == '*' || c == '/') return 1;
return -1;
}
private int solveRPN(String s) {
String[] strs = s.split(" ");
Deque<BigInteger> stack = new LinkedList<>();
for (String str : strs) {
if (str.equals("")) {
continue;
}
if ("+-*/".indexOf(str) != -1) {
BigInteger num2 = stack.pop();
BigInteger num1 = stack.pop();
if (str.equals("+")) {
stack.push(num1.add(num2));
} else if (str.equals("-")) {
stack.push(num1.subtract(num2));
} else if (str.equals("*")) {
stack.push(num1.multiply(num2));
} else if (str.equals("/")) {
stack.push(num1.divide(num2));
}
} else {
stack.push(new BigInteger(str));
}
}
return stack.pop().intValue();
}
}
note that: in the solveRPN(), I use BigInteger class, because we may encounter big number.