三刷 07/2022
Version #1 Stack
自己凭直觉写了一遍，看了一下没有第一次写的时候简洁
用了一个Node Object代表string 和数字
写了一个bug就是因为我只检查stack顶端是不是数字来和当前数字相连，所以遇到2[2[这种情况就会判断成为22
而且我的方法没有利用到“[”的case，直接continue了
其实可以利用“'[”来进行入栈的操作，只有遇到"["才把数字push进去，应该会简单很多
Time O(N)?
?? 2[2[2[2[2[2['a']]]]]
Time Complexity: \mathcal{O}(\text{maxK} \cdot n)O(maxK⋅n), where \text{maxK}maxK is the maximum value of kk and nn is the length of a given string ss. We traverse a string of size nn and iterate kk times to decode each pattern of form \text{k[string]}k[string]. This gives us worst case time complexity as \mathcal{O}(\text{maxK} \cdot n)O(maxK⋅n).
Space O(N)
Runtime: 2 ms, faster than 58.11% of Java online submissions for Decode String.
Memory Usage: 41.8 MB, less than 74.45% of Java online submissions for Decode String.
class Solution {
class Node {
public int val;
public String str;
public boolean isNum;
public Node(int val) {
this.val = val;
this.isNum = true;
}
public Node(String str) {
this.str = str;
}
}
public String decodeString(String s) {
Stack<Node> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int val = c - '0';
if (!stack.isEmpty() && stack.peek().isNum && Character.isDigit(s.charAt(i - 1))) {
val += stack.pop().val * 10;
}
stack.push(new Node(val));
continue;
}
if (c == '[') {
continue;
}
if (c == ']') {
StringBuilder sb = new StringBuilder();
String str = stack.pop().str;
// System.out.printf("str=%s\n", str);
int cnt = stack.pop().val;
while (cnt-- > 0) {
sb.append(str);
}
pushString(stack, sb.toString());
continue;
}
pushString(stack, "" + c);
}
return stack.pop().str;
}
private void pushString(Stack<Node> stack, String str) {
String prev = "";
if (!stack.isEmpty() && !stack.peek().isNum) {
prev = stack.pop().str;
}
stack.push(new Node(prev + str));
}
}
53.83 %
class Solution {
public String decodeString(String s) {
if (s == null || s.length() == 0) {
return s;
}
Deque<Integer> nums = new ArrayDeque<>();
Deque<String> chars = new ArrayDeque<>();
int i = 0;
char curr;
StringBuilder sb = new StringBuilder();
while (i < s.length()) {
curr = s.charAt(i);
if (Character.isDigit(curr)) {
int num = curr - '0';
while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
num = num * 10 + s.charAt(i + 1) - '0';
i++;
}
nums.addFirst(num);
} else if (curr == '[') {
chars.addFirst(sb.toString());
sb.setLength(0);
} else if (curr == ']') {
int count = nums.isEmpty() ? 1 : nums.removeFirst();
String repeat = sb.toString();
while (count-- > 1) {
sb.append(repeat);
}
sb.insert(0, chars.removeFirst());
} else {
sb.append(curr);
}
i++;
}
return sb.toString();
}
}
一刷
感觉写一个Stack<Object>也是可以的，但是每次要判断的太多，没有必要
两个Stack一个是count一个是StringBuilder
遇到"["就把之前的StringBuilder和数字压栈
遇到"]"就pop且和之前的parent StringBuilder连在一起
这里的initialize是初始化一个最开始的容器StringBuilder，放最终的结果然后return
如果没有初始化的容器而只当遇到"["才new StringBuilder的话很显然是不对的
因为edge case比较少所以一遍就写过了
40.18 %
class Solution {
public String decodeString(String s) {
if (s == null) return s;
Stack<StringBuilder> sStack = new Stack<>();
Stack<Integer> cStack = new Stack<>();
int count = 0;
StringBuilder curr = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
count = count * 10 + Character.getNumericValue(c);
} else if (c == '[') {
cStack.push(count);
count = 0;
sStack.push(curr);
curr = new StringBuilder();
} else if (c == ']') {
int repeat = cStack.pop();
StringBuilder prev = sStack.pop();
while (repeat-- > 0) {
prev.append(curr);
}
curr = prev;
} else {
curr.append(c);
}
}
return curr.toString();
}
}
No comments:
Post a Comment