Squeeze function squeeze(s1,s2)..... Suggestion Required......

Question

Hi,

I want to write a squeeze functions squeeze(s1,s2) that deletes each character in s1 that matches any character in string s2.

Is there any algorithm available apart from time complexity(m * n) i.e. traversing string s1 m times(length of s2) and skipping all those characters occurring in s2.

Thanks...

Answer 1

Create a bitmap (bool array).

Traverse string s2, toggling each bit corresponding to a character.

Traverse string s1, skipping the character if the corresponding bit is true.

Obviously modify the length if you want to allow more characters (the example below requires a ToLower()/ToUpper() as it uses 26).

A rough C# Proof of Concept Example (ready to paste in LINQPad):

void Main()
{
    // Mapping the alpha lower case characters to start at zero
    int magicAsciiAdjust = -96; 

    string s1 = "asdaswerwe"; // Assumes no non-alpha
    string s2 = "asdacbBe"; // Assumes no non-alpha
    string output = String.Empty;

    bool[] mask = new bool[26];
    foreach (char c in s2.ToLower())
    {
        mask[((int)c) + magicAsciiAdjust] = true;
    }
    foreach(char c in s1.ToLower())
    {
        if (!mask[((int)c) + magicAsciiAdjust])
            output += c;
    }
    output.Dump();
}

You could support ASCII by making your mask 128 long. (and removing the ToLower() calls) etc.

Answer 2

Using a Set

private static String squeeze(String s1, String s2) {
    StringBuilder sb = new StringBuilder(); 
    HashSet<Character> set = new HashSet<Character>();
    for(char c: s2.toCharArray()) set.add(c);
    for(char c: s1.toCharArray())
        if(!set.contains(c))
            sb.append(c);
    return sb.toString();
}

---

Using a Bit Array

private static String squeeze(String s1, String s2) {
        StringBuilder sb = new StringBuilder(); 
        BitSet bs = new BitSet(256);
        for(char c: s2.toCharArray()) bs.set(c);
        for(char c: s1.toCharArray())
            if(!bs.get(c))
                sb.append(c);
        return sb.toString();
    }

---

//Example

String s1 = "badcode";
String s2 = "abcd";
String squeezed = squeeze(s1,s2);

Output: oe