FilesExpand file tree

 master

/

DecodeString.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

68 lines (64 loc) · 2.24 KB

 master

/

DecodeString.java

Copy path

Top

File metadata and controls

• Code
• Blame

68 lines (64 loc) · 2.24 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

61

62

63

64

65

66

67

68

package stack;

import java.util.Stack;

/**

* Created by gouthamvidyapradhan on 12/04/2018. Given an encoded string, return it's decoded

* string.

*

* <p>The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets

* is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

*

* <p>You may assume that the input string is always valid; No extra white spaces, square brackets

* are well-formed, etc.

*

* <p>Furthermore, you may assume that the original data does not contain any digits and that digits

* are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

*

* <p>Examples:

*

* <p>s = "3[a]2[bc]", return "aaabcbc". s = "3[a2[c]]", return "accaccacc". s = "2[abc]3[cd]ef",

* return "abcabccdcdcdef".

*

* <p>Solution: Maintain a stack and push items when a character other than ] is encountered. When a

* character ] is encountered pop elements, build string and duplicate it.

*/

public class DecodeString {

/**

* Main method

*

* @param args

* @throws Exception

*/

public static void main(String[] args) throws Exception {

System.out.println(new DecodeString().decodeString("100[leetcode]"));

}

public String decodeString(String s) {

Stack<Character> stack = new Stack<>();

for (int i = 0; i < s.length(); i++) {

if (s.charAt(i) == ']') {

StringBuilder stackBuff = new StringBuilder();

while (stack.peek() != '[') {

stackBuff.append(stack.pop());

}

stack.pop(); // pop '['

String num = "";

while (!stack.isEmpty() && !Character.isAlphabetic(stack.peek()) && stack.peek() != '[') {

num = stack.pop() + num;

}

String str = stackBuff.reverse().toString();

StringBuilder stringMultiple = new StringBuilder();

int N = Integer.parseInt(num);

while (N-- > 0) {

stringMultiple.append(str);

}

for (int j = 0; j < stringMultiple.length(); j++) {

stack.push(stringMultiple.charAt(j));

}

} else stack.push(s.charAt(i));

}

StringBuilder result = new StringBuilder();

while (!stack.isEmpty()) {

result.append(stack.pop());

}

return result.reverse().toString();

}

}