FilesExpand file tree

 master

/

DecodeString.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

60 lines (54 loc) · 1.58 KB

 master

/

DecodeString.java

Copy path

Top

File metadata and controls

• Code
• Blame

60 lines (54 loc) · 1.58 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

package leetcode;

import java.util.Stack;

/**

* Project Name : Leetcode

* Package Name : leetcode

* File Name : DecodeString

* Creator : Edward

* Date : Sep, 2017

* Description : TODO

*/

public class DecodeString {

/**

* 394. Decode String

* s = "3[a]2[bc]", return "aaabcbc".

s = "3[a2[c]]", return "accaccacc".

s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

time : O(n);

space : O(n);

* @param s

* @return

*/

public String decodeString(String s) {

if (s == null || s.length() == 0) return s;

String res = "";

Stack<Integer> countStack = new Stack<>();

Stack<String> resStack = new Stack<>();

int idx = 0;

while (idx < s.length()) {

if (Character.isDigit(s.charAt(idx))) {

int count = 0;

while (Character.isDigit(s.charAt(idx))) {

count = count * 10 + (s.charAt(idx) - '0');

idx++;

}

countStack.push(count);

} else if (s.charAt(idx) == '[') {

resStack.push(res);

res = "";

idx++;

} else if (s.charAt(idx) == ']') {

StringBuilder temp = new StringBuilder(resStack.pop());

int time = countStack.pop();

for (int i = 0; i < time; i++) {

temp.append(res);

}

res = temp.toString();

idx++;

} else {

res += s.charAt(idx++);

}

}

return res;

}

}