Блог

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

У меня есть функция, которая принимает 2 строки, предположим, «common» и «cmn». Оно должно возвращать значение True, основанное на том факте, что ‘c’, ‘m’, ‘n’ встречаются в том же порядке в «common». Но если бы аргументы были «общими» и «omn», это вернуло бы False, потому что, хотя они встречаются в том же порядке, но ‘m’ также появляется после ‘o’ (что не соответствует условию соответствия шаблону)

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

Надеемся на передышку в stackoverflow! 🙂

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

Я думаю, что это довольно просто. Запустите шаблон и перед каждым символом получите индекс его последнего появления в строке. Индекс всегда должен увеличиваться, иначе возвращается 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 , и алгоритм был бы быстрее.

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

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

Требование:

Давайте рассмотрим тот же пример ‘common’ (основная строка) и ‘cmn’ (подстрока). Сначала нам нужно прояснить, что любые символы могут повторяться в основной строке, а также в подстроке, и поскольку ее шаблон, на котором мы концентрируемся, индекс символа играет большую роль. Итак, нам нужно знать:

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

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

• c -> o
• c -> m
• c -> n
• o -> m
• o -> o
• o -> n
• m -> m
• m -> o
• m -> n
• o -> n

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

Решение

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

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

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

1. Установите флаг как False
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, я не отправлял код. Но кто-нибудь может попробовать реализовать мою идею

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

Создайте функцию «Check», которая принимает 2 строки в качестве аргументов. Проверьте каждый символ строки 2 в строке 1. Порядок появления каждого символа s2 должен быть проверен как true в 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;
}
}
  

Разве это не выполнимо в 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 amp;amp; 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;
}
  

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

 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
  

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

 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] amp;amp; 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

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

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

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

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

В общей форме построение регулярного выражения должно быть примерно в следующих строках.

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

например:

demmn -> d.*e[^d]*m[^e]*m[^m] *n

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

сопоставление шаблонов открытого класса {

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

}