Функция сжатия squeeze (s1, s2) ..... Требуется предложение

Question

Я хочу написать функцию сжатия squeeze (s1, s2), которая удаляет каждый символ в s1, который соответствует любому символу в строке s2.

Есть ли какой-либо алгоритм, доступный кроме временной сложности (m * n)т.е. обход строки s1 m раз (длина s2) и пропуск всех тех символов, которые встречаются в s2.

Спасибо ...

Answer 1

Создание растрового изображения (массив bool).

Строка перемещения s2, переключение каждого бита, соответствующего символу.

Строка перемещения s1, пропуск символа, если соответствующий бит равен true.

Очевидно, измените длину, если вы хотите разрешить больше символов (в приведенном ниже примере требуется ToLower () / ToUpper (), поскольку он использует 26).

Пример грубого подтверждения концепции на C # (готово)вставить в 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();
}

Вы можете поддерживать ASCII, сделав маску длиной 128.(и удаление вызовов ToLower ()) и т. д.

Answer 2

Использование набора

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();
}

---

Использование битового массива

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();
    }

---

// Пример

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

Выход : oe