Remove Duplicate Letters

  • It’s interesting to learn that Stack also has `contains()` method

A common technique for processing counts of characters: use s.charAt(i) - 'a' as index for that char and accumulate its count.

Inspired by this post: https://discuss.leetcode.com/topic/34074/easy-understanding-10m-stack-java-solution

public String removeDuplicateLetters(String s) {
if(s == null || s.length() == 0) return s;

int[] dict = new int[26];
char[] chars = s.toCharArray();
for(int i = 0; i < s.length(); i++){
dict[chars[i] - 'a'] += 1;
}

Stack<Character> stack = new Stack();
int i = 0;
while(i < s.length()){
char current = chars[i];
int index = dict[current - 'a'];
//only take care of new characters that are not on the stack yet
if(!stack.contains(current)) {
while(!stack.isEmpty() && current <= stack.peek() && dict[stack.peek() - 'a'] >= 1){
stack.pop();
}
if(!stack.contains(current)){
stack.push(current);
}
}
dict[current - 'a']--;
i++;
}

StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pop());
}
return sb.reverse().toString();
}

Advertisements

Basic Calculator

https://leetcode.com/problems/basic-calculator/

Completely my original idea, cool!

Ideas:

  1. Filter the string first, get rid of spaces, and group multi-digit numbers into one string
  2. push every string into stack1, until we encounter “)”, then we pop everything from stack1 onto stack2 until we encounter the first “(” from stack1, then we pop everything from stack2 to do the calculation, when the calculation is done, we push the intermediate result back to stack1, continue the loop until the end of the string array.
  3. when exiting, there are two possible cases:
    1. there’s only one element in stack1, then we could simply pop it as return value;
    2. there could be a simple expression (without any open or close parentheses there any more), in this case, we just do the calculation again and return that value.
public int calculate(String s) {
if (s == null || s.isEmpty())
return 0;

s = s.replaceAll("\\s", "");
char[] chars = s.toCharArray();
List<String> filteredStr = new ArrayList<String>();
for(int i = 0; i < chars.length;){
StringBuilder sb = new StringBuilder();
while (i < chars.length && Character.isDigit(chars[i])) {
sb.append(chars[i]);
i++;
}
if (i == chars.length) {
if (sb.toString().length() != 0) {
filteredStr.add(sb.toString());
}
} else {
if (sb.toString().length() != 0) {
filteredStr.add(sb.toString());
}
if(chars[i] == '+' || chars[i] == '-' || chars[i] == '(' || chars[i] == ')'){
filteredStr.add(String.valueOf(chars[i]));
}
i++;
}
}

Stack<String> stack1 = new Stack();
Stack<String> stack2 = new Stack();
for(int i = 0; i < filteredStr.size();){
while(i < filteredStr.size() && !filteredStr.get(i).equals(")")){
stack1.push(filteredStr.get(i));
i++;
}
if(i != filteredStr.size()){
while(!stack1.isEmpty() && !stack1.peek().equals("(")){
stack2.push(stack1.pop());
}
stack1.pop();//this is to pop "(" since we use peek in the above while condition
int exp = 0;
while(!stack2.isEmpty()){
if(stack2.size() == 1){
stack1.push(stack2.pop());
break;
}
int operand1 = Integer.parseInt(stack2.pop());
String operator = stack2.pop();
int operand2 = Integer.parseInt(stack2.pop());
if(operator.equals("+")) exp = operand1 + operand2;
else if(operator.equals("-")) exp = operand1 - operand2;
stack2.push(String.valueOf(exp));
}
i++;
}
}

if(stack1.size() == 1) return Integer.parseInt(stack1.pop());

while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
while(!stack2.isEmpty()){
if(stack2.size() == 1){
stack1.push(stack2.pop());
break;
}
int exp = 0;
int operand1 = Integer.parseInt(stack2.pop());
String operator = stack2.pop();
int operand2 = Integer.parseInt(stack2.pop());
if(operator.equals("+")) exp = operand1 + operand2;
else if(operator.equals("-")) exp = operand1 - operand2;
stack2.push(String.valueOf(exp));
}
return Integer.parseInt(stack1.pop());
}

Basic Calculator II

Completely my original idea, it took me literally more than 4 hours to debug step by step, but I believe it’s worth of it.

Keys:

  • Must use String.equals() to do string comparison!!!! Do not use “==“!!!
  • Get rid of ” ” from the input string and group multi-digit numbers into one string and store the result into an array of Strings because I’ll have to access str[i+1], if it’s multi-digit number, I’ll only get its left-most digit which is wrong.
  • Do division and multiplication in the first round since they have higher precedence.
  • Reverse the stack to get the left-to-right order since the order for addition and subtraction matters
  • then in the new stack, do addition and subtraction.

 

public int calculate(String s) {
if (s == null || s.isEmpty())
return 0;

Stack<String> stack = new Stack();
s = s.replaceAll("\\s", "");
char[] chars = s.toCharArray();
List<String> filteredStr = new ArrayList<String>();
for(int i = 0; i < chars.length;){
StringBuilder sb = new StringBuilder();
while (i < chars.length && Character.isDigit(chars[i])) {
sb.append(chars[i]);
i++;
}
if (i == chars.length) {
if (sb.toString().length() != 0) {
filteredStr.add(sb.toString());
}
} else {
if (sb.toString().length() != 0) {
filteredStr.add(sb.toString());
}
if(chars[i] == '+' || chars[i] == '-' || chars[i] == '*' || chars[i] == '/'){
filteredStr.add(String.valueOf(chars[i]));
}
i++;
}
}

for(int i = 0; i < filteredStr.size(); i++){
if(!filteredStr.get(i).equals("*") &&
!filteredStr.get(i).equals("/")) {
stack.push(filteredStr.get(i));
}
else {
if(!stack.isEmpty()){
int exp = 0;
int operand = Integer.parseInt(stack.pop());
if(filteredStr.get(i).equals("*")){
exp = operand * Integer.parseInt(filteredStr.get(i+1));
} else if(filteredStr.get(i).equals("/")){
exp = operand / Integer.parseInt(filteredStr.get(i+1));
}
stack.push(String.valueOf(exp));
i++;
}
}
}

//move everything from this stack into a new stack to get everything from left to right since cases like this: String s = "1-1+1" cannot be calculated from right to left, which means 1-(1+1) = -1, but the correct answer is actually 1, so we'll have to reverse the stack
Stack<String> newStack = new Stack();
while(!stack.isEmpty()){
newStack.push(stack.pop());
}

while (!newStack.isEmpty()) {
if (newStack.size() == 1)
return Integer.parseInt((newStack.pop()));
int operand1 = Integer.parseInt(newStack.pop());
String operator = newStack.pop();
int operand2 = Integer.parseInt(newStack.pop());
long exp = 0;
if (operator.equals("+")) {
exp = operand2 + operand1;
} else if (operator.equals("-")) {
exp = operand1 - operand2;
}
newStack.push(String.valueOf(exp));
}

return Integer.parseInt((newStack.pop()));
}

Valid Parentheses

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

Now, this problem could be solved with ease, note: this one MUST be solved with a stack, counter trick won’t work because this problem has different types of parentheses, including, ()[]{}, and the order of these parentheses matters.

This is different from the newly added problem here: https://leetcode.com/problems/remove-invalid-parentheses/ where dietpepsi@ pointed out that we could save the space cost by not using a stack to check if a string is a valid parentheses.

public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
char[] chars = s.toCharArray();
for(char c : chars){
if(c == '(' || c == '[' || c == '{'){
stack.push(c);
} else if(c == ')'){
if(stack.isEmpty()) return false;
else if(stack.pop() != '(') return false;
} else if(c == ']'){
if(stack.isEmpty()) return false;
else if(stack.pop() != '[') return false;
} else if(c == '}'){
if(stack.isEmpty()) return false;
else if(stack.pop() != '{') return false;
}
}
return stack.isEmpty();
}

Evaluate Reverse Polish Notation

https://leetcode.com/problems/evaluate-reverse-polish-notation/

Hooray, I made it AC’ed completely by myself, just hold on there, don’t give up, you’ll get things figured out. This will prove to be 100 times more effective and last longer in your memory than you just go to Discuss and read others’ solution. Easier said than done! Cheers!

  • Using Queue to implement this is a natural choice since apparently it obeys the FILO order.
  • The other key is how to handle the on-the-fly expression (calculation result), e.g. given this input: [“4″,”-2″,”/”,”2″,”-3″,”-“,”-“], how to handle the result of (4/(-2)) ? Very intuitively, I thought of pushing it back to the stack, and it solved this problem!! Cool! I’m getting the sense of programming little by little!
public int evalRPN(String[] tokens) {
Stack<String> stack = new Stack<String>();
Set<String> op = new HashSet<String>();
op.add("+");
op.add("-");
op.add("*");
op.add("/");

int exp = 0;
String operand1 = "";
String operand2 = "";
for (int i = 0; i < tokens.length;) {
while ((i < tokens.length) && (!op.contains(tokens[i]))) {
stack.push(tokens[i]);
i++;
}
if (i == tokens.length) {
if (!stack.isEmpty()) {
return Integer.parseInt(stack.pop());
}
} else if (op.contains(tokens[i])) {
operand2 = stack.pop();
operand1 = stack.pop();
if (tokens[i].equals("+")) {
exp = Integer.parseInt(operand1) + Integer.parseInt(operand2);
} else if (tokens[i].equals("-")) {
exp = Integer.parseInt(operand1) - Integer.parseInt(operand2);
} else if (tokens[i].equals("*")) {
exp = Integer.parseInt(operand1) * Integer.parseInt(operand2);
} else {
exp = Integer.parseInt(operand1) / Integer.parseInt(operand2);
}
stack.push(String.valueOf(exp));
i++;
}
}
return Integer.parseInt(stack.pop());
}