Given a
string of some symbols, write a program to transform a string by repeatedly
eliminating two same symbols occurring together.
For example
1. “ABCCAB”
is transformed to “ABAB”
2. “ABCCBD”
is transformed to “AD”
“ABCCBD” -> “ABBD” -> “AD”
We can solve
this problem using stack data structure.
1.
Read
String character by character.
If top element of stack is equal to this character,
then pop it, else push this character.
Repeat above procedure until end of
the string, finally stack contains our output.
import java.util.LinkedList; import java.util.Objects; public class StringCouple { public static String decoupleString(String str) { Objects.nonNull(str); if (str.length() < 2) return str; LinkedList<Character> list = new LinkedList<>(); list.push(str.charAt(0)); for (int i = 1; i < str.length(); i++) { if (list.size() > 0 && list.peek() == str.charAt(i)) { list.pop(); } else { list.push(str.charAt(i)); } } StringBuilder sb = new StringBuilder(list.size()); for (Character c : list) sb.append(c); return sb.reverse().toString(); } }
Following is
the junit test case for above program.
import static org.junit.Assert.*; import org.junit.*; public class StringCoupleTest { @Test public void test1(){ assertEquals(StringCouple.decoupleString("ABCCAB"), "ABAB"); assertEquals(StringCouple.decoupleString("ABCCBD"), "AD"); assertEquals(StringCouple.decoupleString("GBRRBR"), "GR"); assertEquals(StringCouple.decoupleString("BGRGRR"), "BGRG"); assertEquals(StringCouple.decoupleString("GGBB"), ""); assertEquals(StringCouple.decoupleString("RGBGBR"), "RGBGBR"); } }
No comments:
Post a Comment