Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
String utilities
String utilities
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.stringutils.StringUtils;
import static org.junit.Assert.assertEquals;
public class CompressJTests {
String input, output;
@Test
//null or empty
public void nullEmpty() {
input = null;
output = null;
assertEquals("null string expected null", output, StringUtils.stringCompress(input));
input = "";
output = "";
assertEquals("empty string expected empty", output, StringUtils.stringCompress(input));
input = new String();
output = new String();
assertEquals("new string expected new String", output, StringUtils.stringCompress(input));
}
@Test
public void noCompress() {
input = "abcdefg";
output = "abcdefg";
assertEquals("abcdefg string expected abcdefg", output, StringUtils.stringCompress(input));
input = "aaabcdefg";
output = "aaabcdefg";
assertEquals("aaabcdefg string expected aaabcdefg", output, StringUtils.stringCompress(input));
}
@Test
public void withCompress() {
input = "aaaaaahhtt";
output = "a6h2t2";
assertEquals("aaaaaahhtt string expected a6h2t2", output, StringUtils.stringCompress(input));
input = " ";
output = " 3";
assertEquals(" string expected 3", output, StringUtils.stringCompress(input));
input = "AAAAAAA!!bcdefg MMMMM";
output = "A7!2b1c1d1e1f1g1 2M5";
assertEquals("AAAAAAA!!bcdefg MMMMM string expected A7!2b1c1d1e1f1g1 2M5", output, StringUtils.stringCompress(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class DecompressJTests {
String input, output;
@Test
//null or empty
public void nullEmpty() {
input = null;
try{
output = StringUtils.decompress(input);
} catch(IllegalArgumentException e){
System.out.println("null string got IllegalArgumentException " + e.getMessage());
}
input = "";
try{
output = StringUtils.decompress(input);
} catch(IllegalArgumentException e){
System.out.println("empty string got IllegalArgumentException " + e.getMessage());
}
input = new String();
try{
output = StringUtils.decompress(input);
} catch(IllegalArgumentException e){
System.out.println("new string got IllegalArgumentException " + e.getMessage());
}
}
@Test
public void noCompress() {
input = "[abcdefg]";
output = "abcdefg";
assertEquals("[abcdefg] string expected abcdefg", output, StringUtils.decompress(input));
input = "[]";
output = "";
assertEquals("[] string expected empty", output, StringUtils.decompress(input));
input = "[][]";
output = "";
assertEquals("[][] string expected empty", output, StringUtils.decompress(input));
input = "1[aaabcdefg]";
output = "aaabcdefg";
assertEquals("1[aaabcdefg] string expected aaabcdefg", output, StringUtils.decompress(input));
}
@Test
public void zeroCompress() {
input = "0[abcdefg][aa]";
output = "aa";
assertEquals("0[abcdefg][aa] string expected aa", output, StringUtils.decompress(input));
input = "[aa]0[abcdefg]";
output = "aa";
assertEquals("[aa]0[abcdefg] string expected aa", output, StringUtils.decompress(input));
}
@Test
public void withCompress() {
input = "3[abc]4[ab]c";
output = "abcabcabcababababc";
assertEquals("3[abc]4[ab]c string expected abcabcabcababababc", output, StringUtils.decompress(input));
input = "2[3[a]b]";
output = "aaabaaab";
assertEquals("2[3[a]b] string expected aaabaaab", output, StringUtils.decompress(input));
input = "2[3[a]b][[cc]0[d]]";
output = "aaabaaabcc";
assertEquals("2[3[a]b][cc0[d]] string expected aaabaaabcc", output, StringUtils.decompress(input));
input = "c";
output = "c";
assertEquals("c string expected c", output, StringUtils.decompress(input));
input = "10[a]";
output = "aaaaaaaaaa";
assertEquals("10[a] string expected aaaaaaaaaa", output, StringUtils.decompress(input));
}
}
package com.blogspot.groglogs.structures;
public class Entry {
public char c;
public int count = 0;
@Override
public boolean equals(Object obj) {
if(obj == null) return false;
if(obj.getClass() != this.getClass()) return false;
Entry other = (Entry) obj;
return this.c == other.c && this.count == other.count;
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class InterleavingJTests {
String a, b, c;
boolean output;
@Test
//null or empty input
public void nullEmpty() {
a = null;
b = null;
c = null;
output = true;
//all null
assertEquals("null, null, null", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, null, null", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "";
c = "";
output = true;
//all empty
assertEquals("empty, empty, empty", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, empty, empty", output, StringUtils.findInterleaveNoDP(a, b, c));
a = null;
b = null;
c = "a";
output = false;
//a,b null
assertEquals("null, null, a", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, null, a", output, StringUtils.findInterleaveNoDP(a, b, c));
a = null;
b = null;
c = "ab";
output = false;
//a,b null
assertEquals("null, null, ab", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, null, ab", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "";
c = "a";
output = false;
//a,b empty
assertEquals("empty, empty, a", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, empty, a", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "";
c = "ab";
output = false;
//a,b empty
assertEquals("empty, empty, ab", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, empty, ab", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "a";
b = null;
c = "a";
output = true;
//b null
assertEquals("a, null, a", output, StringUtils.isInterleave(a, b, c));
assertEquals("a, null, a", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ab";
b = null;
c = "ab";
output = true;
//b null
assertEquals("ab, null, ab", output, StringUtils.isInterleave(a, b, c));
assertEquals("ab, null, ab", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "a";
b = null;
c = "b";
output = false;
//b null
assertEquals("a, null, b", output, StringUtils.isInterleave(a, b, c));
assertEquals("a, null, b", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ab";
b = null;
c = "ac";
output = false;
//b null
assertEquals("ab, null, ac", output, StringUtils.isInterleave(a, b, c));
assertEquals("ab, null, ac", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "a";
b = "";
c = "a";
output = true;
//b empty
assertEquals("a, empty, a", output, StringUtils.isInterleave(a, b, c));
assertEquals("a, empty, a", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ab";
b = "";
c = "ab";
output = true;
//b empty
assertEquals("ab, empty, ab", output, StringUtils.isInterleave(a, b, c));
assertEquals("ab, empty, ab", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "a";
b = "";
c = "c";
output = false;
//b empty
assertEquals("a, empty, c", output, StringUtils.isInterleave(a, b, c));
assertEquals("a, empty, c", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ab";
b = "";
c = "ac";
output = false;
//b empty
assertEquals("ab, empty, ac", output, StringUtils.isInterleave(a, b, c));
assertEquals("ab, empty, ac", output, StringUtils.findInterleaveNoDP(a, b, c));
a = null;
b = "a";
c = "a";
output = true;
//a null
assertEquals("null, a, a", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, a, a", output, StringUtils.findInterleaveNoDP(a, b, c));
a = null;
b = "ab";
c = "ab";
output = true;
//a null
assertEquals("null, ab, ab", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, ab, ab", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "a";
c = "a";
output = true;
//a empty
assertEquals("empty, a, a", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, a, a", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "ab";
c = "ab";
output = true;
//a empty
assertEquals("empty, ab, ab", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, ab, ab", output, StringUtils.findInterleaveNoDP(a, b, c));
a = null;
b = "a";
c = "c";
output = false;
//a null
assertEquals("null, a, c", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, a, c", output, StringUtils.findInterleaveNoDP(a, b, c));
a = null;
b = "ab";
c = "ac";
output = false;
//a null
assertEquals("null, ab, ac", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, ab, ac", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "a";
c = "c";
output = false;
//a empty
assertEquals("empty, a, c", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, a, c", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "ab";
c = "ac";
output = false;
//a empty
assertEquals("empty, ab, ac", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, ab, ac", output, StringUtils.findInterleaveNoDP(a, b, c));
}
@Test
//random
public void randomMatch() {
a = "xy";
b = "x";
c = "xxy";
output = true;
assertEquals("xy, x, xxy", output, StringUtils.isInterleave(a, b, c));
assertEquals("xy, x, xxy", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ABC";
b = "ACA";
c = "ABACCA";
output = true;
assertEquals("ABC, ACA, ABACCA", output, StringUtils.isInterleave(a, b, c));
assertEquals("ABC, ACA, ABACCA", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ABC";
b = "ACA";
c = "ABACAC";
output = true;
assertEquals("ABC, ACA, ABACAC", output, StringUtils.isInterleave(a, b, c));
assertEquals("ABC, ACA, ABACAC", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "A";
b = "A";
c = "AA";
output = true;
assertEquals("A, A, AA", output, StringUtils.isInterleave(a, b, c));
assertEquals("A, A, AA", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AA";
b = "AA";
c = "AAAA";
output = true;
assertEquals("AA, AA, AAAA", output, StringUtils.isInterleave(a, b, c));
assertEquals("AA, AA, AAAA", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AAA";
b = "AAA";
c = "AAAAAA";
output = true;
assertEquals("AAA, AAA, AAAAAA", output, StringUtils.isInterleave(a, b, c));
assertEquals("AAA, AAA, AAAAAA", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AAAA";
b = "AAAA";
c = "AAAAAAAA";
output = true;
assertEquals("AAAA, AAAA, AAAAAAAA", output, StringUtils.isInterleave(a, b, c));
assertEquals("AAAA, AAAA, AAAAAAAA", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AB";
b = "CD";
c = "ABCD";
output = true;
assertEquals("AB, CD, ABCD", output, StringUtils.isInterleave(a, b, c));
assertEquals("AB, CD, ABCD", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AB";
b = "CD";
c = "CDAB";
output = true;
assertEquals("AB, CD, CDAB", output, StringUtils.isInterleave(a, b, c));
assertEquals("AB, CD, CDAB", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AB";
b = "CD";
c = "ACBD";
output = true;
assertEquals("AB, CD, ACBD", output, StringUtils.isInterleave(a, b, c));
assertEquals("AB, CD, ACBD", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AB";
b = "CD";
c = "ACDB";
output = true;
assertEquals("AB, CD, ACDB", output, StringUtils.isInterleave(a, b, c));
assertEquals("AB, CD, ACDB", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AB";
b = "CD";
c = "CADB";
output = true;
assertEquals("AB, CD, CADB", output, StringUtils.isInterleave(a, b, c));
assertEquals("AB, CD, CADB", output, StringUtils.findInterleaveNoDP(a, b, c));
}
@Test
//random
public void randomNotMatch() {
a = "yx";
b = "x";
c = "xxy";
output = false;
assertEquals("yx, x, xxy", output, StringUtils.isInterleave(a, b, c));
assertEquals("yx, x, xxy", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "xxxxx";
b = "xxxxx";
c = "xxxxxxxxxy";
output = false;
assertEquals("xxxxx, xxxxx, xxxxxxxxxy", output, StringUtils.isInterleave(a, b, c));
assertEquals("xxxxx, xxxxx, xxxxxxxxxy", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "xxxxxy";
b = "xxxxxy";
c = "xxxxxxxxxxxy";
output = false;
assertEquals("xxxxxy, xxxxxy, xxxxxxxxxxxy", output, StringUtils.isInterleave(a, b, c));
assertEquals("xxxxxy, xxxxxy, xxxxxxxxxxxy", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "xxxxxy";
b = "xxxxxx";
c = "xxxxxxxxxxyy";
output = false;
assertEquals("xxxxxy, xxxxxx, xxxxxxxxxxyy", output, StringUtils.isInterleave(a, b, c));
assertEquals("xxxxxy, xxxxxx, xxxxxxxxxxyy", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ABC";
b = "ACA";
c = "ABAACC";
output = false;
assertEquals("ABC, ACA, ABAACC", output, StringUtils.isInterleave(a, b, c));
assertEquals("ABC, ACA, ABAACC", output, StringUtils.findInterleaveNoDP(a, b, c));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
import static org.junit.Assert.assertEquals;
public class LongestSubsequenceJTests {
String word, output, out;
List<String> words;
@Test
//null or empty
public void nullEmpty() {
word = null;
words = null;
try{
output = StringUtils.getLongestSubsequence(word, words);
} catch(IllegalArgumentException e){
System.out.println("Null word and list got IllegalArgumentException " + e.getMessage());
}
word = "asd";
words = new ArrayList<>();
try{
output = StringUtils.getLongestSubsequence(word, words);
} catch(IllegalArgumentException e){
System.out.println("Empty list got IllegalArgumentException " + e.getMessage());
}
}
@Test
public void notFound() {
word = "abppplee";
words = new ArrayList<>();
words.add("c");
words.add("cuda");
out = "";
output = StringUtils.getLongestSubsequence(word, words);
assertEquals("word not in list, expected empty", out, output);
word = "b";
words = new ArrayList<>();
words.add("c");
words.add("cuda");
out = "";
output = StringUtils.getLongestSubsequence(word, words);
assertEquals("word not in list, expected empty", out, output);
}
@Test
public void moreSameLength() {
word = "carbot";
words = new ArrayList<>();
words.add("car");
words.add("bot");
out = "car";
output = StringUtils.getLongestSubsequence(word, words);
assertEquals("more word same length in list, expected the first one", out, output);
}
@Test
public void extraChar() {
word = "carbot";
words = new ArrayList<>();
words.add("cara");
words.add("bota");
out = "";
output = StringUtils.getLongestSubsequence(word, words);
assertEquals("one extra char, expected empty", out, output);
}
@Test
public void random() {
word = "abppplee";
words = new ArrayList<>();
words.add("able");
words.add("ale");
words.add("apple");
words.add("bale");
words.add("kangaroo");
out = "apple";
output = StringUtils.getLongestSubsequence(word, words);
assertEquals("random string expected apple", out, output);
word = "abpppalleeoon";
words = new ArrayList<>();
words.add("able");
words.add("ale");
words.add("apple");
words.add("bale");
words.add("kangaroo");
words.add("balloon");
out = "balloon";
output = StringUtils.getLongestSubsequence(word, words);
assertEquals("random string expected balloon", out, output);
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.stringutils.StringUtils;
import static org.junit.Assert.assertEquals;
public class LookAndSayJTests {
int seed, input;
String output;
@Test
public void badInput() {
seed = 1;
input = 0;
try{
output = StringUtils.lookAndSay(seed, input);
}catch(IllegalArgumentException e){
System.out.println("Input 0 got IllegalArgumentException: " + e.getMessage());
}
seed = 1;
input = -1;
try{
output = StringUtils.lookAndSay(seed, input);
}catch(IllegalArgumentException e){
System.out.println("Input -1 got IllegalArgumentException: " + e.getMessage());
}
seed = 0;
input = 1;
try{
output = StringUtils.lookAndSay(seed, input);
}catch(IllegalArgumentException e){
System.out.println("Seed 0 got IllegalArgumentException: " + e.getMessage());
}
seed = -1;
input = 1;
try{
output = StringUtils.lookAndSay(seed, input);
}catch(IllegalArgumentException e){
System.out.println("Seed -1 got IllegalArgumentException: " + e.getMessage());
}
seed = -1;
input = -1;
try{
output = StringUtils.lookAndSay(seed, input);
}catch(IllegalArgumentException e){
System.out.println("Seed -1, input -1 got IllegalArgumentException: " + e.getMessage());
}
}
@Test
public void seed1() {
seed = 1;
input = 1;
output = "1";
assertEquals("1 expected 1", output, StringUtils.lookAndSay(seed, input));
input = 2;
output = "11";
assertEquals("2 expected 11", output, StringUtils.lookAndSay(seed, input));
input = 3;
output = "21";
assertEquals("3 expected 21", output, StringUtils.lookAndSay(seed, input));
input = 4;
output = "1211";
assertEquals("4 expected 1211", output, StringUtils.lookAndSay(seed, input));
input = 5;
output = "111221";
assertEquals("5 expected 111221", output, StringUtils.lookAndSay(seed, input));
input = 6;
output = "312211";
assertEquals("6 expected 312211", output, StringUtils.lookAndSay(seed, input));
input = 7;
output = "13112221";
assertEquals("7 expected 13112221", output, StringUtils.lookAndSay(seed, input));
input = 8;
output = "1113213211";
assertEquals("8 expected 1113213211", output, StringUtils.lookAndSay(seed, input));
input = 9;
output = "31131211131221";
assertEquals("9 expected 31131211131221", output, StringUtils.lookAndSay(seed, input));
}
@Test
public void seed2() {
seed = 2;
input = 1;
output = "2";
assertEquals("1 expected 2", output, StringUtils.lookAndSay(seed, input));
input = 2;
output = "12";
assertEquals("2 expected 12", output, StringUtils.lookAndSay(seed, input));
input = 3;
output = "1112";
assertEquals("3 expected 1112", output, StringUtils.lookAndSay(seed, input));
}
@Test
public void seed22() {
seed = 22;
input = 1;
output = "22";
assertEquals("1 expected 22", output, StringUtils.lookAndSay(seed, input));
input = 2;
output = "22";
assertEquals("2 expected 22", output, StringUtils.lookAndSay(seed, input));
input = 3;
output = "22";
assertEquals("3 expected 22", output, StringUtils.lookAndSay(seed, input));
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.stringutils.StringUtils;
import com.blogspot.groglogs.structures.*;
import static org.junit.Assert.assertEquals;
public class MaxRepCharJTests {
String input;
Entry output;
@Test
//null or empty expected null
public void nullEmpty() {
input = null;
output = null;
assertEquals("null string expected null", output, StringUtils.maxRepChar(input));
input = "";
assertEquals("empty string expected null", output, StringUtils.maxRepChar(input));
input = new String();
assertEquals("new string expected null", output, StringUtils.maxRepChar(input));
}
@Test
public void sameString() {
input = "aaaaa";
output = new Entry();
output.c = 'a';
output.count = 5;
assertEquals("aaaa string expected a,5", output, StringUtils.maxRepChar(input));
input = "t";
output = new Entry();
output.c = 't';
output.count = 1;
assertEquals("t string expected t,1", output, StringUtils.maxRepChar(input));
}
@Test
public void randomString() {
input = "gagggaatttt";
output = new Entry();
output.c = 't';
output.count = 4;
assertEquals("gagggaatttt string expected t,4", output, StringUtils.maxRepChar(input));
input = "some text!!!";
output = new Entry();
output.c = '!';
output.count = 3;
assertEquals("some text!!! string expected !,3", output, StringUtils.maxRepChar(input));
input = "asdfghjkl";
output = new Entry();
output.c = 'a';
output.count = 1;
assertEquals("asdfghjkl string expected a,1", output, StringUtils.maxRepChar(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.stringutils.StringUtils;
import static org.junit.Assert.assertEquals;
public class PalindromeJTests {
String input;
boolean output;
@Test
//null or empty input, expected false
public void nullEmpty() {
input = null;
output = false;
//null
assertEquals("null = null", output, StringUtils.isPalindrome(input));
input = new String();
//empty
assertEquals("empty = null", output, StringUtils.isPalindrome(input));
input = "";
//empty
assertEquals("empty = null", output, StringUtils.isPalindrome(input));
}
@Test
//not palindrome
public void notPalindrome() {
input = "MAN";
output = false;
assertEquals("MAN = false", output, StringUtils.isPalindrome(input));
input = "I am I";
output = false;
assertEquals("I am I = false", output, StringUtils.isPalindrome(input));
input = "I, 12, aM not";
output = false;
assertEquals("I, 12, aM not = false", output, StringUtils.isPalindrome(input));
}
@Test
//not palindrome
public void palindrome() {
input = "A";
output = true;
assertEquals("A = true", output, StringUtils.isPalindrome(input));
input = "MADAM";
output = true;
assertEquals("MADAM = true", output, StringUtils.isPalindrome(input));
input = "Poop";
output = true;
assertEquals("Poop = true", output, StringUtils.isPalindrome(input));
input = "PoOp";
output = true;
assertEquals("PoOp = true", output, StringUtils.isPalindrome(input));
input = "A man, a plan, a canal: Panama";
output = true;
assertEquals("A man, a plan, a canal: Panama = true", output, StringUtils.isPalindrome(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.stringutils.StringUtils;
import java.util.HashSet;
import java.util.Set;
import static org.junit.Assert.assertEquals;
public class PermutateJTests {
String input;
Set<String> output, res;
@Test
//null or empty expected null
public void nullEmpty() {
input = null;
output = null;
assertEquals("null string expected null", output, StringUtils.getPermutations(input));
input = "";
assertEquals("empty string expected null", output, StringUtils.getPermutations(input));
input = new String();
assertEquals("new string expected null", output, StringUtils.getPermutations(input));
}
@Test
public void oneChar() {
input = "a";
output = new HashSet<>();
output.add(input);
res = StringUtils.getPermutations(input);
assertEquals("one character string expected same string", output, res);
assertEquals("multiple same character string expected same string once", 1, res.size());
}
@Test
public void moreSameChar() {
input = "aaa";
output = new HashSet<>();
output.add(input);
res = StringUtils.getPermutations(input);
assertEquals("multiple same character string expected same string", output, res);
assertEquals("multiple same character string expected same string once", 1, res.size());
}
@Test
public void randomNonRepeatingString() {
input = "car";
output = new HashSet<>();
output.add(input);
output.add("cra");
output.add("acr");
output.add("arc");
output.add("rca");
output.add("rac");
res = StringUtils.getPermutations(input);
assertEquals("random non repeating string", output, res);
assertEquals("random non repeating string length 3 expected 6 entries", 6, res.size());
}
@Test
public void randomRepeatingString() {
input = "caa";
output = new HashSet<>();
output.add(input);
output.add("aca");
output.add("aac");
res = StringUtils.getPermutations(input);
assertEquals("random repeating string", output, res);
assertEquals("random repeating string length 3 expected 3 entries", 3, res.size());
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class RegexJTests {
String input, regex;
@Test
//null or empty
public void nullEmpty() {
input = null;
regex = null;
assertEquals("null string and regex expected match", true, StringUtils.matchRegex(input, regex));
input = "";
regex = "";
assertEquals("empty string and regex expected match", true, StringUtils.matchRegex(input, regex));
input = new String();
regex = new String();
assertEquals("new string and new regex expected match", true, StringUtils.matchRegex(input, regex));
}
@Test
//only string or regex is null or empty
public void partialNullEmpty() {
input = null;
regex = "a";
assertEquals("null string and not null regex expected not match", false, StringUtils.matchRegex(input, regex));
input = "a";
regex = "";
assertEquals("not null string and empty regex expected match", true, StringUtils.matchRegex(input, regex));
}
@Test
//invalid regex, expected exception
public void invalidRegex() {
input = "a";
regex = "a$a"; //$ in the wrong place
boolean out;
int expected_errors = 0, gotten_errors = 0;
try{
expected_errors++;
out = StringUtils.matchRegex(input, regex);
} catch(IllegalArgumentException e){
gotten_errors++;
System.out.println("$ in the wrong place got IllegalArgumentException " + e.getMessage());
}
input = "a";
regex = "a^"; //^ in the wrong place
try{
expected_errors++;
out = StringUtils.matchRegex(input, regex);
} catch(IllegalArgumentException e){
gotten_errors++;
System.out.println("^ in the wrong place got IllegalArgumentException " + e.getMessage());
}
input = "a";
regex = "a["; //invalid character
try{
expected_errors++;
out = StringUtils.matchRegex(input, regex);
} catch(IllegalArgumentException e){
gotten_errors++;
System.out.println("invalid character [ got IllegalArgumentException " + e.getMessage());
}
input = "a";
regex = "*1"; //* in the wrong place
try{
expected_errors++;
out = StringUtils.matchRegex(input, regex);
} catch(IllegalArgumentException e){
gotten_errors++;
System.out.println("* in the wrong place got IllegalArgumentException " + e.getMessage());
}
input = "a";
regex = "^*"; //* does not follow . or alphanumeric character
try{
expected_errors++;
out = StringUtils.matchRegex(input, regex);
} catch(IllegalArgumentException e){
gotten_errors++;
System.out.println("* does not follow . or alphanumeric character got IllegalArgumentException " + e.getMessage());
}
assertEquals("Got as many errors as expected", expected_errors, gotten_errors);
}
@Test
public void matches() {
input = "a";
regex = "a";
assertEquals("a matches a", true, StringUtils.matchRegex(input, regex));
input = "aaa";
regex = "a*";
assertEquals("aaa matches a*", true, StringUtils.matchRegex(input, regex));
input = "aW9";
regex = "aW9";
assertEquals("aW9 matches aW9", true, StringUtils.matchRegex(input, regex));
input = "aW9bcW";
regex = "aW9";
assertEquals("aW9bcW matches aW9", true, StringUtils.matchRegex(input, regex));
input = "ab8aW9";
regex = "aW9";
assertEquals("ab8aW9 matches aW9", true, StringUtils.matchRegex(input, regex));
input = "cc2aW9raW9z";
regex = "aW9";
assertEquals("cc2aW9raW9z matches aW9", true, StringUtils.matchRegex(input, regex));
input = "ab9w";
regex = "a.9.";
assertEquals("ab9w matches a.9.", true, StringUtils.matchRegex(input, regex));
input = "ac9bcW";
regex = "a.9.";
assertEquals("ac9bcW matches a.9.", true, StringUtils.matchRegex(input, regex));
input = "ab8a999";
regex = "a.9.";
assertEquals("ab8a999 matches a.9.", true, StringUtils.matchRegex(input, regex));
input = "cc2aW9r";
regex = "a.9.";
assertEquals("cc2aW9r matches a.9.", true, StringUtils.matchRegex(input, regex));
input = "a9";
regex = "aW*9";
assertEquals("a9 matches aW*9", true, StringUtils.matchRegex(input, regex));
input = "aW9";
regex = "aW*9";
assertEquals("aW9 matches aW*9", true, StringUtils.matchRegex(input, regex));
input = "aWW9b9cW";
regex = "aW*9";
assertEquals("aWW9b9cW matches aW*9", true, StringUtils.matchRegex(input, regex));
input = "aU9aWW9";
regex = "aW*9";
assertEquals("aU9aWW9 matches aW*9", true, StringUtils.matchRegex(input, regex));
input = "ab8aWWW9W9aa";
regex = "aW*9";
assertEquals("ab8aWWW9W9aa matches aW*9", true, StringUtils.matchRegex(input, regex));
input = "cc2a9raW9zWW9ac";
regex = "aW*9";
assertEquals("cc2a9raW9zWW9ac matches aW*9", true, StringUtils.matchRegex(input, regex));
input = "a9";
regex = "a.*9";
assertEquals("a9 matches a.*9", true, StringUtils.matchRegex(input, regex));
input = "aZ9";
regex = "a.*9";
assertEquals("aZ9 matches a.*9", true, StringUtils.matchRegex(input, regex));
input = "aZW9b9cW";
regex = "a.*9";
assertEquals("aZW9b9cW matches a.*9", true, StringUtils.matchRegex(input, regex));
input = "aU9a9";
regex = "a.*9";
assertEquals("aU9a9 matches a.*9", true, StringUtils.matchRegex(input, regex));
input = "b8aWUW9W";
regex = "a.*9";
assertEquals("b8aWUW9W matches a.*9", true, StringUtils.matchRegex(input, regex));
input = "cc2a9raU9z";
regex = "a.*9";
assertEquals("cc2a9raU9z matches a.*9", true, StringUtils.matchRegex(input, regex));
input = "ceaW999zb34b3az";
regex = "aW9*.b3";
assertEquals("ceaW999zb34b3az matches aW9*.b3", true, StringUtils.matchRegex(input, regex));
input = "ceaW9b34";
regex = "aW9*.b3";
assertEquals("ceaW9b34 matches aW9*.b3", true, StringUtils.matchRegex(input, regex));
input = "pqaWzb38q";
regex = "aW9*.b3";
assertEquals("pqaWzb38q matches aW9*.b3", true, StringUtils.matchRegex(input, regex));
input = "aW99zer";
regex = "^aW.9";
assertEquals("aW99zer matches ^aW.9", true, StringUtils.matchRegex(input, regex));
input = "aWW9";
regex = "^aW.9";
assertEquals("aWW9 matches ^aW.9", true, StringUtils.matchRegex(input, regex));
input = "aWP9GA";
regex = "^aW.9";
assertEquals("aWP9GA matches ^aW.9", true, StringUtils.matchRegex(input, regex));
input = "aWW9";
regex = "aW.9$";
assertEquals("aWW9 matches aW.9$", true, StringUtils.matchRegex(input, regex));
input = "aWW9abcaWz9";
regex = "aW.9$";
assertEquals("aWW9abcaWz9 matches aW.9$", true, StringUtils.matchRegex(input, regex));
input = "baaWX9";
regex = "aW.9$";
assertEquals("baaWX9 matches aW.9$", true, StringUtils.matchRegex(input, regex));
input = "abcaWP9";
regex = "aW.9$";
assertEquals("abcaWP9 matches aW.9$", true, StringUtils.matchRegex(input, regex));
input = "aW9";
regex = "^aW9$";
assertEquals("aW9 matches ^aW9$", true, StringUtils.matchRegex(input, regex));
}
@Test
public void notMatches() {
input = "a";
regex = "b";
assertEquals("a not matches b", false, StringUtils.matchRegex(input, regex));
input = "aaa";
regex = "a*b";
assertEquals("aaa not matches a*b", false, StringUtils.matchRegex(input, regex));
input = "aW8";
regex = "aW9";
assertEquals("aW8 not matches aW9", false, StringUtils.matchRegex(input, regex));
input = "bcd8";
regex = "aW9";
assertEquals("bcd8 not matches aW9", false, StringUtils.matchRegex(input, regex));
input = "az9";
regex = "a.9.";
assertEquals("az9 not matches a.9.", false, StringUtils.matchRegex(input, regex));
input = "a989a";
regex = "a.9.";
assertEquals("a989a not matches a.9.", false, StringUtils.matchRegex(input, regex));
input = "bac9";
regex = "a.9.";
assertEquals("bac9 not matches a.9.", false, StringUtils.matchRegex(input, regex));
input = "aWWU9";
regex = "aW*9";
assertEquals("aWWU9 not matches aW*9", false, StringUtils.matchRegex(input, regex));
input = "baX9";
regex = "aW*9";
assertEquals("baX9 not matches aW*9", false, StringUtils.matchRegex(input, regex));
input = "aXW9Wa";
regex = "aW*9";
assertEquals("aXW9Wa not matches aW*9", false, StringUtils.matchRegex(input, regex));
input = "9UWaW8";
regex = "a.*9";
assertEquals("9UWaW8 not matches a.*9", false, StringUtils.matchRegex(input, regex));
input = "b9aaaX";
regex = "a.*9";
assertEquals("b9aaaX not matches a.*9", false, StringUtils.matchRegex(input, regex));
input = "XUq8";
regex = "a.*9";
assertEquals("XUq8 not matches a.*9", false, StringUtils.matchRegex(input, regex));
input = "ceaW98zb34";
regex = "aW9*.b3";
assertEquals("ceaW98zb34 not matches aW9*.b3", false, StringUtils.matchRegex(input, regex));
input = "pqaW988b38q";
regex = "aW9*.b3";
assertEquals("pqaW988b38q not matches aW9*.b3", false, StringUtils.matchRegex(input, regex));
input = "baWx9";
regex = "^aW.9";
assertEquals("baWx9 not matches ^aW.9", false, StringUtils.matchRegex(input, regex));
input = "aW9";
regex = "^aW.9";
assertEquals("aW9 not matches ^aW.9", false, StringUtils.matchRegex(input, regex));
input = "aWcc90";
regex = "^aW.9";
assertEquals("aWcc90 not matches ^aW.9", false, StringUtils.matchRegex(input, regex));
input = "aWW99";
regex = "aW.9$";
assertEquals("aWW99 not matches aW.9$", false, StringUtils.matchRegex(input, regex));
input = "aW";
regex = "aW.9$";
assertEquals("aW not matches aW.9$", false, StringUtils.matchRegex(input, regex));
input = "aWcc90";
regex = "aW.9$";
assertEquals("aWcc90 not matches aW.9$", false, StringUtils.matchRegex(input, regex));
input = "aaW9";
regex = "^aW9$";
assertEquals("aaW9 not matches ^aW9$", false, StringUtils.matchRegex(input, regex));
input = "aW9aW9";
regex = "^aW9$";
assertEquals("aW9aW9 not matches ^aW9$", false, StringUtils.matchRegex(input, regex));
input = "aW99";
regex = "^aW9$";
assertEquals("aW99 not matches ^aW9$", false, StringUtils.matchRegex(input, regex));
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.stringutils.StringUtils;
import static org.junit.Assert.assertEquals;
public class ReplaceSpaceJTests {
String input, output;
@Test
//null or empty expected null
public void nullEmpty() {
input = null;
output = null;
assertEquals("null string expected null", output, StringUtils.replaceSpace(input));
input = "";
assertEquals("empty string expected null", output, StringUtils.replaceSpace(input));
input = new String();
assertEquals("new string expected null", output, StringUtils.replaceSpace(input));
}
@Test
public void noSpace() {
input = "aaaaa";
output = "aaaaa";
assertEquals("aaaa string expected aaaaa", output, StringUtils.replaceSpace(input));
input = "t!";
output = "t!";
assertEquals("t! string expected t!", output, StringUtils.replaceSpace(input));
}
@Test
public void withSpace() {
input = "ga ggg aatttt";
output = "ga%20ggg%20aatttt";
assertEquals("ga ggg aatttt string expected ga%20ggg%20aatttt", output, StringUtils.replaceSpace(input));
input = " ";
output = "%20%20%20";
assertEquals(" string expected %20%20%20", output, StringUtils.replaceSpace(input));
input = "Some long string with little sense and lots of spaces";
output = "Some%20long%20string%20with%20little%20sense%20and%20lots%20of%20spaces";
assertEquals("Some long string with little sense and lots of spaces string expected Some%20long%20string%20with%20little%20sense%20and%20lots%20of%20spaces", output, StringUtils.replaceSpace(input));
}
}
package com.blogspot.groglogs.stringutils;
import com.blogspot.groglogs.structures.*;
import java.util.*;
public class StringUtils {
public static final char REGEX_MATCH_ANY = '.';
public static final char REGEX_MATCH_MANY = '*';
public static final char REGEX_MATCH_AT_START = '^';
public static final char REGEX_MATCH_AT_END = '$';
public static boolean isPalindrome(String s){
if(s == null || s.length() < 1)return false;
for(int i = 0, j = s.length() - 1; j > i; ){
if(!Character.isLetterOrDigit(s.charAt(i))){
i++;
continue;
}
if(!Character.isLetterOrDigit(s.charAt(j))){
j--;
continue;
}
if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))return false;
else{
i++;
j--;
}
}
return true;
}
public static String stringCompress(String s){
if(s == null || s.length() <= 1) return s;
int[] counts = new int[s.length()];
char[] chars = new char[s.length()];
char c;
int j = 0;
counts[0] = 1;
chars[0] = s.charAt(0);
//for each character in string, count how many times it appears
for(int i = 1; i < s.length(); i++){
c = s.charAt(i);
if(c == chars[j]) counts[j]++;
else{
j++;
chars[j] = c;
counts[j] = 1;
}
}
//if we compressed the string a bit, then our arrays have some space left, mark the premature end
if(j < counts.length - 1) counts[++j] = -1;
//we do not want to create a new String everytime while we concatenate
StringBuilder sb = new StringBuilder();
j = 0;
while(j < counts.length){
if(counts[j] == -1) break;
//for each character in original string, concatenate it alongside the number of occurrences
sb.append(chars[j]);
sb.append(counts[j]);
j++;
}
//if the compressed string is longer, return original string instead
if(sb.length() > s.length()) return s;
return sb.toString();
}
public static String replaceSpace(String s){
if(s == null || s.length() == 0) return null;
int space_count = 0;
char c;
//count how many white spaces we have
for(int i = 0; i < s.length(); i++){
c = s.charAt(i);
if(c == ' ') space_count++;
}
if(space_count == 0) return s;
//allocate space for new string replacement. CAREFUL: we replace 1 char with 3 so we need 2 extra spaces!
char[] res = new char[s.length() + space_count * 2];
//prepare result string. CAREFUL: can't use same index otherwise we skip characters in either string or char[]
for(int i = 0, j = 0; j < s.length(); i++, j++){
c = s.charAt(j);
if(c == ' '){
res[i] = '%';
res[++i] = '2';
res[++i] = '0';
}
else res[i] = c;
}
return new String(res);
}
public static Entry maxRepChar(String s){
Entry max = new Entry(), curr = new Entry();
char c;
if(s == null || s.length() == 0) return null;
//initialize with first item in string
curr.count = 0;
curr.c = s.charAt(0);
max.count = 0;
for(int i = 0; i < s.length(); i++){
c = s.charAt(i);
/*
keep incrementing the current counter for the item we're evaluating now
as long as we have a subsequent uninterrupted stream
*/
if(c == curr.c) curr.count++;
else{
/*
when we interrupt the stream, check if the item we're evaluating
appeared more times than the current maximum, if so, set it as max
*/
if(curr.count > max.count){
max.count = curr.count;
max.c = curr.c;
}
//and reset the counter for current item
curr.c = c;
curr.count = 1;
}
}
//don't miss the case when the max run until end of string
if(curr.count > max.count){
max.count = curr.count;
max.c = curr.c;
}
return max;
}
/*
The look and say sequence is generated by starting with a seed number
then looking at the digits of the number and describing how many of each consecutive ones there are
Eg with seed 1:
1 -> one 1
11 -> two 1
21 -> one 2, one 1
To get the nth in the sequence, we generate all of them :(
*/
public static String lookAndSay(int seed, int n){
if(seed <= 0) throw new IllegalArgumentException("Seed must be greater than 0: " + seed);
if(n <= 0) throw new IllegalArgumentException("Input must be greater than 0: " + n);
//we collect here the final and intermediate outputs
String res = "" + seed;
StringBuilder sb;
char c;
int i = 1, curr_count;
while(i < n){
sb = new StringBuilder();
c = res.charAt(0);
curr_count = 1;
//pick the first character in the partial output and start counting how many times does it appear
for(int j = 1; j < res.length(); j++){
if(res.charAt(j) == c) curr_count++;
//as soon as we encounter a different character, update the result and reset the counter
else{
sb.append(String.valueOf(curr_count) + c);
c = res.charAt(j);
curr_count = 1;
}
}
i++;
//do not forget the last append!
sb.append(String.valueOf(curr_count) + c);
//update the partial output
res = sb.toString();
}
return res;
}
//Generate all permutations for a given string, skipping duplicates. Recursive implementation
private static void permutate(int size, StringBuilder curr, StringBuilder left, Set<String> out){
StringBuilder sb = new StringBuilder(curr);
//if we built the full string, add it to the result and return
if(left.length() == 0){
//we might not have any more characters left to choose from, but the string can still be incomplete!
if(sb.length() == size) out.add(sb.toString());
return;
}
//foreach remaining character, add it to the current string, then recurse on the remaining ones leaving that out
for(int i = left.length() - 1; i >= 0; i--){
StringBuilder next = new StringBuilder(curr);
next.append(left.charAt(i));
//deleteCharAt if used on left itself will alter it permanently and not return a new object!
StringBuilder rest = new StringBuilder(left).deleteCharAt(i);
permutate(size, next, rest, out);
}
}
public static Set<String> getPermutations(String s){
if(s == null || s.isEmpty()) return null;
Set<String> permutations = new HashSet<>();
permutate(s.length(), new StringBuilder(), new StringBuilder(s), permutations);
return permutations;
}
/*
Given a string and a list of words, find the longest word that can be created from the input string
by only skipping characters from it
*/
public static String getLongestSubsequence(String s, List<String> words){
if(s == null || words == null || s.isEmpty() || words.isEmpty()) throw new IllegalArgumentException("Input string and word list cannot be null or empty!");
//key is the next character we need to find to move further in a word
//value is a map (could also be a list of tuples) of words we are building up for which that is the next character we need
//with the indication of the length matched so far. If we ever build the full word, we check it and track it as longest in case
//then keep iterating until the String has been parsed entirely
HashMap<Character, Map<String, Integer>> nextCharsForWord = new HashMap<>();
String currLongest = "";
//prepare structure
for(String word : words){
Character c = word.charAt(0);
//get map, create one if no entry exists yet
Map<String, Integer> m = nextCharsForWord.get(c);
if(m == null) m = new HashMap<>();
//add word to map and put it in next character map
m.put(word, 0);
nextCharsForWord.put(c, m);
}
//loop over each character in input string and match, if possible, with the known next required characters from the value map
//for every match, reorganise the map so that the word is tracked in the value map corresponding to the next character we need
for(Character c: s.toCharArray()){
//get words that need this character next
Map<String, Integer> m = nextCharsForWord.get(c);
//no work for non required characters
if(m != null){
//check each word that need this character
Iterator<Map.Entry<String, Integer>> iter = m.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry<String, Integer> e = iter.next();
String word = e.getKey();
Integer len = e.getValue();
//if word is complete, remove it from the search and track if it's the longest so far
if (word.length() == len + 1) {
iter.remove();
if(word.length() > currLongest.length()) currLongest = word;
continue;
}
//otherwise increment found counter for it and place it in the value map for the search of the next character
Character nextChar = e.getKey().charAt(e.getValue() + 1);
Map<String, Integer> nextWords = nextCharsForWord.get(nextChar);
if(nextWords == null) nextWords = new HashMap<>();
nextWords.put(word, len + 1);
nextCharsForWord.put(nextChar, nextWords);
}
}
}
return currLongest;
}
/*
Given a string in the format k[content], convert it to a string made of k repetitions of content
this can be nested
0 means empty string
no k means 1
*/
public static String decompress(String s){
if(s == null || s.isEmpty()) throw new IllegalArgumentException("String cannot be empty or null!");
//we will keep track of the parsing and elaboration progress in a stack
Stack<String> parsed = new Stack<>();
StringBuilder curr = new StringBuilder();
//start building up the stack for each character in the string
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
switch (c){
case '[':
//maybe we just found a number, push it to the stack
String rep = curr.toString();
//or maybe it was null, therefore assume 1 repetition
if(rep.length() == 0) rep = "1";
parsed.push(rep);
parsed.push("["); //we will use this marker to match against the respective close parenthesis
curr = new StringBuilder();
break;
case ']':
//process the current expression - everything we have so far until the matching open parenthesis
String tmp = curr.toString();
curr = new StringBuilder();
curr.append(tmp);
//reverse append until we find the start bracket
//this is because we are walking the stack top to bottom
//every new element actually comes before us
while(parsed.peek() != "["){
curr.insert(0, parsed.pop());
}
parsed.pop();//get rid of bracket
//find the number of repetitions we need to perform
int repetitions = Integer.parseInt(parsed.pop());
//if we have to, repeat the string
if(repetitions != 0) {
tmp = curr.toString();
curr = new StringBuilder();
for (int j = 0; j < repetitions; j++) {
curr.append(tmp);
}
parsed.push(curr.toString());
}
else parsed.push(""); //otherwise throw everything away
curr = new StringBuilder();
break;
default:
curr. append(c);
}
}
//when we reach the end of the string, we might still have pieces on the stack to assemble
//keep the last string piece we read so far (will be the last piece of the final string)
String tmp = curr.toString();
curr = new StringBuilder();
curr.append(tmp);
//prepend all the other pieces, if any, we calculated to create the result string
while(!parsed.empty()){
curr.insert(0, parsed.pop());
}
return curr.toString();
}
//helper for matchRegex
private static boolean isMatch(String s, String regex){
//we finished the matching without returning false, before so we matched all
if(regex == null || regex.length() == 0) return true;
//invalid regex, ^ is not at the beginning (checked before) or * is found without a preceding . or alphanumeric character
if(regex.charAt(0) == REGEX_MATCH_AT_START) throw new IllegalArgumentException("Invalid regex, " + REGEX_MATCH_AT_START + " not found at the beginning!");
if(regex.charAt(0) == REGEX_MATCH_MANY) throw new IllegalArgumentException("Invalid regex, " + REGEX_MATCH_MANY + " not preceded by " + REGEX_MATCH_ANY + " or alphanumeric character!");
//check if we were asked to match at the end with $, it means the string has to be fully consumed by now
//otherwise we matched the whole string but are not at the ned
if(regex.charAt(0) == REGEX_MATCH_AT_END){
//invalid regex, $ is not at the end
if(regex.length() != 1) throw new IllegalArgumentException("Invalid regex, $ found before the end!");
return s.length() == 0;
}
//check if we have a * now, means must match whatever alphanumeric character before it (or any if it's a .)
//could also match 0 instances of it. In both cases we need to keep processing the rest of the regex
//at SOME point afterwards
if(regex.length() > 1 && regex.charAt(1) == REGEX_MATCH_MANY){
//see if we can match 1+ instances of the character
char match = regex.charAt(0);
//for any valid match of the *, check if the rest of the string already matches the rest of the regex
//CAUTION! the condition on match MUST be in the cycle conditions and NOT inside
//since we want to proceed only as long as we can keep matching the char before the *
for(int i = 0; i < s.length() && (match == REGEX_MATCH_ANY || match == s.charAt(i)); i++){
if(isMatch(s.substring(i + 1), regex.substring(2))) return true;
}
//if we had 0 matches from the *, which is allowed, check if the rest of the string matches the rest of the regex
return isMatch(s, regex.substring(2));
}
//only thing left is an alphanumeric or . character at the beginning of the regex
//any other character is an exception
if(!(regex.charAt(0) == REGEX_MATCH_ANY) && !Character.isLetterOrDigit(regex.charAt(0))) throw new IllegalArgumentException("Invalid regex, expected alphanumeric character or " + REGEX_MATCH_ANY + " but found: " + regex.charAt(0));
//if we still have matches to perform but the string is finished, we can't match the regex
if(s.length() == 0) return false;
//if we have a . or a character, check if the character matches the expected one and moe on to the next match
if(regex.charAt(0) == REGEX_MATCH_ANY || regex.charAt(0) == s.charAt(0)) return isMatch(s.substring(1), regex.substring(1));
//character match failed, expression cannot be matched
return false;
}
/*
Following syntax is allowed
alphanumeric - matches exactly that character
. - matches any character
* - must follow . or an alphanumeric character, means we can match multiple instances of the preceding character
^ - must be the first character, means the matching has to begin from the start
$ - must be the last character, means the matching has to occur at the end
in the absence of ^ and $, the match can occur anywhere in the string
*/
public static boolean matchRegex(String s, String regex){
//empty string is only matched my empty regex
if((s == null || s.length() == 0) && (regex != null && regex.length() > 0)) return false;
//empty regex matches all strings
if(regex == null || regex.length() == 0) return true;
//check if we need to match from the beginning
if(regex.charAt(0) == REGEX_MATCH_AT_START) return isMatch(s, regex.substring(1));
//else we need to evaluate the matching starting at every place
for(int i = 0; i < s.length(); i++) {
if(isMatch(s.substring(i), regex)) return true;
}
//whole string processed, no match found
return false;
}
/*
A string is the result of interleaving two other strings if it contains ALL character from both strings in the same order
as they appear in the sources. You can pick at each time 0+ characters from either string!
Eg:
ABACCA is the interleaving of ABC and ACA -> AB, A, C, CA
ABACAC is also the interleaving of ABC and ACA -> AB, AC, A, C
ABAACC is NOT the interleaving of ABC and ACA -> AB, A, we expect now a C but find an A instead
*/
//version with no DP structure
public static boolean findInterleaveNoDP(String a, String b, String c){
//all null or empty strings are interleaved
if(c == null || c.isEmpty()) return (a == null || a.isEmpty()) && (b == null || b.isEmpty());
//if one string is null, other two must match
if(a == null || a.isEmpty()) return c.equals(b);
if(b == null || b.isEmpty()) return c.equals(a);
//if length does not add up, for sure no interleave
if(c.length() != a.length() + b.length()) return false;
boolean a_match = false, b_match = false;
//since we can get 0+ characters from either string, explore both possibilities if any of the two matches the current
//character in the result. If there is no match, since order is important, for sure we eliminate that branch
//the two strings can match in multiple ways as well, we just need to find one
if(c.charAt(0) == a.charAt(0)){
a_match = findInterleaveNoDP((a.length() > 1) ? a.substring(1) : null, b, (c.length() > 1) ? c.substring(1) : null);
}
//no need to continue if we found a match already
if(a_match) return true;
if(c.charAt(0) == b.charAt(0)){
b_match = findInterleaveNoDP(a, (b.length() > 1) ? b.substring(1) : null, (c.length() > 1) ? c.substring(1) : null);
}
return b_match;
}
//helper for isInterleave
private static boolean findInterleave(String a, String b, String c, int a_idx, int b_idx, Boolean[][] a_matches, Boolean[][] b_matches){
//if one string is null, other two must match, this is our base case
if(a == null) return c.equals(b);
if(b == null) return c.equals(a);
boolean a_match = false, b_match = false;
//if we already have calculated this scenario, get the value from the cache
//otherwise compute it and store it later. Do this for both strings due to the 0+ matching condition
//but if we have a lot of overlapping we can recycle work already done
if(a_matches[a_idx][b_idx] != null){
a_match = a_matches[a_idx][b_idx];
} else if(c.charAt(0) == a.charAt(0)){
//if they do not match we have initialized to false anyway
//avoid index out of range by checking first before the substring operation
//advance the index for each string alternatively. It is only used for checking the cache
a_match = findInterleave((a.length() > 1) ? a.substring(1) : null, b, (c.length() > 1) ? c.substring(1) : null, a_idx + 1, b_idx, a_matches, b_matches);
}
a_matches[a_idx][b_idx] = a_match;
//no need to continue if we found a match already
if(a_match) return true;
if(b_matches[b_idx][a_idx] != null){
b_match = b_matches[b_idx][a_idx];
} else if(c.charAt(0) == b.charAt(0)){
b_match = findInterleave(a, (b.length() > 1) ? b.substring(1) : null, (c.length() > 1) ? c.substring(1) : null, a_idx, b_idx + 1, a_matches, b_matches);
}
b_matches[b_idx][a_idx] = b_match;
return b_match;
}
public static boolean isInterleave(String a, String b, String c) {
//all null or empty strings are interleaved
if(c == null || c.isEmpty()) return (a == null || a.isEmpty()) && (b == null || b.isEmpty());
//if one string is null, other two must match
//we will repeat this as base case in the inner function too
//it's here so that we skip other operations if this situation appears immediately
if(a == null || a.isEmpty()) return c.equals(b);
if(b == null || b.isEmpty()) return c.equals(a);
//if length does not add up, for sure no interleave
if(c.length() != a.length() + b.length()) return false;
//keep two structures where we mark for each index in each string if we found a match from that combination
//for both strings, so that when we process them later we recycle work already done
//this is useful when the two strings overlap in many places
Boolean[][] a_matches = new Boolean[a.length()][b.length()];
Boolean[][] b_matches = new Boolean[b.length()][a.length()];
return findInterleave(a, b, c, 0, 0, a_matches, b_matches);
}
}
You can’t perform that action at this time.