Соответствие вхождению и шаблону символов String2 в String1

Question

Мне задали этот вопрос в телефонном интервью для летней стажировки, и я попытался придумать решение сложности n * m (хотя и не совсем точное) на Java.

У меня есть функция, которая принимает 2 строки, предположим, "общие" и "CMN". Он должен возвращать True, основываясь на том факте, что «c», «m», «n» встречаются в том же порядке в «общем». Но если бы аргументы были «общие» и «омн», он вернул бы «Ложь», потому что, хотя они встречаются в одном и том же порядке, но «м» также появляется после «о» (что не соответствует условию сопоставления с образцом)

Я работал над этим, используя Hashmaps и Ascii, но пока не получил убедительного решения! Из того, что я читал до сих пор, это может быть связано с алгоритмами Бойера-Мура или Левенштейна?

Надеясь на передышку в стеке! :)

Редактировать : в некоторых ответах говорится об уменьшении длины слова или создании хэш-набора. Но, насколько я понимаю, этот вопрос не может быть решен с помощью хэш-наборов, потому что вхождение / повторение каждого символа в первой строке имеет свое значение. Условия PASS - «con», «cmn», «cm», «cn», «mn», «on», «co». Сбой при условии, что может показаться иначе - «com», «omn», «mon», «om». Это FALSE / FAIL, потому что «o» встречается как до, так и после «m». Другой пример - "google", "ole" будет PASS, но "google", "gol" потерпит неудачу, потому что "o" также появляется перед "g"!

Answer 1

Я думаю, это довольно просто. Пройдите по шаблону, и каждый символ получит индекс своего последнего вхождения в строке. Индекс должен всегда увеличиваться, в противном случае вернуть false. Так в псевдокоде:

index = -1
foreach c in pattern
    checkindex = string.lastIndexOf(c)
    if checkindex == -1                   //not found
        return false
    if checkindex < index
        return false
    if string.firstIndexOf(c) < index     //characters in the wrong order
        return false
    index = checkindex
return true

Редактировать: вы можете улучшить код, передав index в качестве начального индекса методу lastIndexOf. Тогда вам не придется сравнивать checkindex с index, и алгоритм будет быстрее.

Обновлено: Исправлена ​​ошибка в алгоритме. Добавлено дополнительное условие для учета порядка букв в шаблоне.

Answer 2

Отличный вопрос и пара часов исследований, и я думаю, что нашел решение. Прежде всего позвольте мне попытаться объяснить вопрос в другом подходе.

Требования:

Давайте рассмотрим один и тот же пример 'common' (mainString) и 'cmn' (subString). Во-первых, нам нужно прояснить, что любые символы могут повторяться в пределах mainString, а также в SubString, и, поскольку его шаблон, на котором мы концентрируемся, индекс символа играет большую роль. Итак, нам нужно знать:

• Индекс символа (наименьший и самый высокий)

Позволяет держать это в ожидании, а затем еще раз проверить паттерны. Для слова common нам нужно выяснить, присутствует ли конкретный шаблон cmn или нет. Возможны различные варианты с общим: - (применяется приоритет)

• с -> о
• с -> м
• c -> n
• о -> м
• o -> o
• o -> n
• м -> м
• м -> о
• м -> n
• o -> n

В любой момент времени этот приоритет и сравнение должны быть действительными. Поскольку приоритет играет огромную роль, нам нужно иметь индекс каждого уникального символа вместо хранения различных шаблонов.

Решение

Первая часть решения заключается в создании хэш-таблицы по следующим критериям: -

1. Создать хеш-таблицу с ключом в качестве каждого символа mainString
2. Каждая запись для уникального ключа в хэш-таблице будет хранить два индекса, то есть lowerIndex и upperIndex
3. Выполните цикл по mainString и для каждого нового символа обновите новую запись lowerIndex в Hash с текущим индексом символа в mainString.
4. Если происходит столкновение, обновите текущий индекс с помощью записи более высокого индекса, делайте это до конца строки

Вторая и основная часть сопоставления с образцом: -

1. Установить флаг как ложный
2. Цикл по подстроке и для каждый символ как ключ, отступление подробности из хэша.
3. Сделайте то же самое для следующего персонажа.

4. Непосредственно перед приращением цикла проверьте два условия

   If highestIndex(current character) > highestIndex(next character) Then
      Pattern Fails, Flag <- False, Terminate Loop
      // This condition is applicable for almost all the cases for pattern matching
   
   Else If lowestIndex(current character) > lowestIndex(next character) Then
      Pattern Fails, Flag <- False, Terminate Loop
      // This case is explicitly for cases in which patterns like 'mon' appear
   

5. Показать флаг

N.B .: Поскольку я не настолько универсален в Java, я не представил код. Но кто-то может попытаться реализовать мою идею

Answer 3

Я сам сделал этот вопрос неэффективно, но он дает точный результат!Буду признателен, если кто-нибудь сможет разобрать эффективный код / ​​алгоритм из этого!

Создайте функцию «Проверка», которая принимает 2 строки в качестве аргументов.Проверьте каждый символ строки 2 в строке 1. Порядок появления каждого символа s2 должен быть проверен как истинный в S1.

1. Взять символ 0 из строки p и пройти через строку s, чтобы найтиего индекс первого вхождения.
2. Пройдите через заполненный массив ascii, чтобы найти любое значение, большее, чем индекс первого вхождения.
3. Пройдите далее, чтобы найти последнее вхождение, и обновите массив ascii
4. Взять символ 1 из строки p и пройти через строку s, чтобы найти индекс первого вхождения в строке s
5. Перейти через заполненный массив ascii, чтобы найти любое значение, превышающее индекс первого вхождения,если найдено, верните False.
6. Пройдите дальше, чтобы найти последнее вхождение, и обновите массив ascii

Как можно заметить, это метод грубой силы ... Я думаю, O(N ^ 3)

public class Interview
{
    public static void main(String[] args)
{
    if (check("google", "oge"))
        System.out.println("yes");
    else System.out.println("sorry!");
}

 public static boolean check (String s, String p) 
{   

     int[] asciiArr =  new int[256];    
     for(int pIndex=0; pIndex<p.length(); pIndex++) //Loop1 inside p
     {
        for(int sIndex=0; sIndex<s.length(); sIndex++) //Loop2 inside s
        {
            if(p.charAt(pIndex) == s.charAt(sIndex))    
            {
                asciiArr[s.charAt(sIndex)] = sIndex; //adding char from s to its Ascii value

                for(int ascIndex=0; ascIndex<256; )     //Loop 3 for Ascii Array
                {
                    if(asciiArr[ascIndex]>sIndex)           //condition to check repetition
                    return false;
                    else ascIndex++;
                }
            }
        }
     }
    return true;
}
}

Answer 4

Я сам попробовал по-другому.Просто делюсь своим решением.

открытый класс PatternMatch {

public static boolean matchPattern(String str, String pat) {

    int slen = str.length();
    int plen = pat.length();
    int prevInd = -1, curInd;
    int count = 0;

    for (int i = 0; i < slen; i++) {

        curInd = pat.indexOf(str.charAt(i));


        if (curInd != -1) {

            if(prevInd == curInd)
                continue;
            else if(curInd == (prevInd+1))
                count++;
            else if(curInd == 0)
                count = 1;
            else count = 0;

            prevInd = curInd;
        }


        if(count == plen)
            return true;

    }

    return false;
}

public static void main(String[] args) {

    boolean r = matchPattern("common", "on");
    System.out.println(r);
}

}

Answer 5

Я думаю, что это не проверка ваших основ компьютерных наук, больше того, что вы бы практически делали в среде программирования Java.

Вы могли бы создать регулярное выражение из второго аргумента, т. Е. ...

omn -> o.*m[^o]*n

..., а затем протестируйте строку-кандидат для этого, используя String.matches (...) илииспользуя класс Pattern .

В общем виде, конструкция RegExp должна быть следующей по следующим строкам:

exp -> in [0] . * + Для каждого x: 2 -> in.lenght {( in [x-1] + [^ in [x-2]] * + in [x] )}

, например:

demmn -> d. * E [^ d] * m [^ e]* м [^ м] * н

Answer 6

Я бы посчитал это одним из худших фрагментов кода, который я когда-либо писал, или одним из худших примеров кода в stackoverflow ... но угадайте, что ... все ваши условия выполнены!
Ни один алгоритм не мог бы действительно удовлетворить потребности, поэтому я просто использовал грубую силу ... проверить это ...
И мне просто наплевать на сложность пространства и времени ... Моей целью было сначала попытаться решить ее ... и, возможно, улучшить ее позже!

public class SubString {

    public static void main(String[] args) {
        SubString ss = new SubString();
        String[] trueconditions = {"con", "cmn", "cm", "cn", "mn", "on", "co" };
        String[] falseconditions = {"com", "omn", "mon", "om"};

        System.out.println("True Conditions : ");
        for (String str : trueconditions) {
            System.out.println("SubString? : " + str + " : " + ss.test("common", str));
        }
        System.out.println("False Conditions : ");
        for (String str : falseconditions) {
            System.out.println("SubString? : " + str + " : " + ss.test("common", str));
        }
        System.out.println("SubString? : ole : " + ss.test("google", "ole"));
        System.out.println("SubString? : gol : " + ss.test("google", "gol"));
    }

    public boolean test(String original, String match) {
        char[] original_array = original.toCharArray();
        char[] match_array = match.toCharArray();

        int[] value = new int[match_array.length];
        int index = 0;
        for (int i = 0; i < match_array.length; i++) {
            for (int j = index; j < original_array.length; j++) {
                if (original_array[j] != original_array[j == 0 ? j : j-1] && contains(match.substring(0, i), original_array[j])) {

                    value[i] = 2;
                } else {
                    if (match_array[i] == original_array[j]) {
                        if (value[i] == 0) {
                            if (contains(original.substring(0, j == 0 ? j : j-1), match_array[i])) {
                                value[i] = 2;
                            } else {
                                value[i] = 1;
                            }
                        }
                        index = j + 1;
                    }
                }
            }
        }
        for (int b : value) {
            if (b != 1) {
                return false;
            }
        }
        return true;
    }

    public boolean contains(String subStr, char ch) {
        for (char c : subStr.toCharArray()) {
            if (ch == c) {
                return true;
            }
        }
        return false;
    }
}

-IvarD

Answer 7

public class StringPattern {
    public static void main(String[] args) {
        String inputContainer = "common";
        String inputContainees[] = { "cmn", "omn" };
        for (String containee : inputContainees)
            System.out.println(inputContainer + " " + containee + " "
                    + containsCommonCharsInOrder(inputContainer, containee));

    }

    static boolean containsCommonCharsInOrder(String container, String containee) {
        Set<Character> containerSet = new LinkedHashSet<Character>() {
            // To rearrange the order
            @Override
            public boolean add(Character arg0) {
                if (this.contains(arg0))
                    this.remove(arg0);
                return super.add(arg0);
            }
        };
        addAllPrimitiveCharsToSet(containerSet, container.toCharArray());
        Set<Character> containeeSet = new LinkedHashSet<Character>();
        addAllPrimitiveCharsToSet(containeeSet, containee.toCharArray());

        // retains the common chars in order
        containerSet.retainAll(containeeSet);
        return containerSet.toString().equals(containeeSet.toString());

    }

    static void addAllPrimitiveCharsToSet(Set<Character> set, char[] arr) {
        for (char ch : arr)
            set.add(ch);
    }

}

Выход:

common cmn true
common omn false

Answer 8

Разве это невозможно в O (n log n)?

Шаг 1, уменьшите строку, удалив все символы, которые отображаются справа.Строго говоря, вам нужно исключать символы только в том случае, если они появляются в проверяемой вами строке.

/** Reduces the maximal subsequence of characters in container that contains no
 * character from container that appears to the left of the same character in
 * container.  E.g. "common" -> "cmon", and "whirlygig" -> "whrlyig".
 */
static String reduceContainer(String container) {
  SparseVector charsToRight = new SparseVector();  // Like a Bitfield but sparse.
  StringBuilder reduced = new StringBuilder();
  for (int i = container.length(); --i >= 0;) {
    char ch = container.charAt(i);
    if (charsToRight.add(ch)) {
      reduced.append(ch);
    }
  }
  return reduced.reverse().toString();
}

Шаг 2, проверка содержимого.

static boolean containsInOrder(String container, String containee) {
  int containerIdx = 0, containeeIdx = 0;
  int containerLen = container.length(), containeeLen == containee.length();
  while (containerIdx < containerLen && containeeIdx < containeeLen) {
    // Could loop over codepoints instead of code-units, but you get the point...
    if (container.charAt(containerIdx) == containee.charAt(containeeIdx)) {
      ++containeeIdx;
    }
    ++containerIdx;
  }
  return containeeIdx == containeeLen;
}

И чтобы ответить на ваш второй вопрос,нет, расстояние Левенштейна вам не поможет, поскольку у него есть свойство, что если вы меняете аргументы, результат остается тем же, а требуемый алгоритм - нет.