шаблон слова без регулярных выражений

Question

Мне недавно задали этот вопрос в одном из интервью:

"По заданному шаблону и вводу строки - выясните, соответствует ли строка тому же шаблону, и верните true или false."

Примеры:

1. Шаблон: «abba», ввод: «красно-синий» должен возвращать 1.
2. Шаблон: «аааа», ввод: «asdasdasdasd» должен возвращаться 1.
3. Pattern: "aabb", input: "xyzabcxzyabc" должен возвращать 0.

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

Если да, может кто-нибудь объяснить мне подробно грубая сила против эффективного способа решить эту проблему?На мой взгляд, это был довольно сложный вопрос.

Answer 1

Довольно просто проверить строку, если вы знаете длину подстрок, соответствующих каждому символу шаблона.

Уловка для эффективной реализации может заключаться в минимизации количества назначений длины, которое вам необходимоcheck.

Для каждого шаблона и тестовой строки существует линейное диофантово уравнение, ограничивающее возможные назначения длины:

Шаблон aaaa с длиной строки 16 ⇒ 4a = 16 ⇒ a = 4

Шаблон abba с длиной строки 14 ⇒ 2a + 2b = 14 ⇒ a + b = 7

и т. Д.

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

Есть еще виды входных данных (множество букв-шаблонов с длинными строками), которые приводят к экспоненциальной сложностиОднако ... но все остальные рабочие ответы здесь (в настоящее время) имеют эту проблемусе.

Answer 2

Я бы подошел к этому следующим образом:

• рассмотрим первый символ в шаблоне ('a' в первом примере)

• поскольку «а» до сих пор неизвестно, предположим длину для шаблона «а» (первоначально 1, что соответствует «r»)

• перейти к следующему символу в шаблоне ('b ')

• , поскольку «b» до сих пор неизвестно, предположить длину для шаблона «b» (первоначально «1», что соответствует «e»)

• перейти к следующему символу в шаблоне ('b')

• , поскольку «b» уже известно как «e», его можно сравнить сследующий кусок, "д".Здесь у нас есть ошибка, и нам нужно вернуться к первому вхождению шаблона 'b' и повторить попытку со следующей длиной (2,3, ..., пока не останется места).

• если для 'b' не было совпадения, вернитесь к первому вхождению 'a'.

Этот процесс продолжается до тех пор, пока не будет исчерпана строка или не найдено совпадениебыл найден для всех шаблонов.

Это может быть реализовано с помощью рекурсивной процедуры, которая принимает в качестве входных данных

• текущего шаблона,
• набора гипотетических шаблонов исоответствующие подстроки,
• хвост строки.

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

Если текущий шаблон уже выдвинут, проверьте соответствие строки в текущей позиции.Если есть совпадение, рекурсивно продолжайте поиск, если вы не находитесь в конце строки и не сделали этого.

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

Если совпадений нет, и это не первое вхождение этого шаблона, верните идентификаторнесоответствующий образец.(При выполнении рекурсивного вызова, если возвращаемое значение указывает на сбой, сравните возвращенный идентификатор шаблона с текущим и верните его вызывающей стороне, если он отличается.)

'a', 'a'= "r", "edbluebluered"
    'b', 'a'= "r", 'b'= "e", "dbluebluered" => mismatch "e" <-> "d"
    'b', 'a'= "r", 'b'= "ed", "bluebluered" => mismatch "ed" <-> "bl"
    'b', 'a'= "r", 'b'= "edb", "luebluered" => mismatch "edb" <-> "lue"
    ...
'a', 'a'= "re", "dbluebluered"
    'b', 'a'= "re", 'b'= "d", "bluebluered" => mismatch "d" <-> "b"
    'b', 'a'= "re", 'b'= "db", "luebluered" => mismatch "db" <-> "lu"
    ...
'a', 'a'= "red", "bluebluered"
    'b', 'a'= "red", 'b'= "b", "luebluered" => mismatch "b" <-> "l"
    'b', 'a'= "red", 'b'= "bl", "uebluered" => mismatch "bl" <-> "ue"
    'b', 'a'= "red", 'b'= "blu", "ebluered" => mismatch "blu" <-> "ebl"
    'b', 'a'= "red", 'b'= "blue", "bluered"
        'b', 'a'= "red", 'b'= "blue", "red"
            'b', 'a'= "red", 'b'= "blue", "" done !

Условие "больше места нет"может быть просто реализовано путем проверки длины хвоста строки и сравнения с текущей длиной шаблона, но лучшая оценка возможна путем накопления длин всех гипотетических шаблонов для всех их вхождений в строке шаблона.Например, если мы выдвинули гипотезу «a» = «bl» и «b» = «uer», строка шаблона «abba» предсказывает длину по крайней мере 10.

Answer 3

Хороший вопрос.Я попробовал простой способ без рекурсий.Сначала я проверяю, какие буквы в шаблоне существуют.Затем я создаю все подстроки ввода.На третьем шаге я создаю все комбинации шаблонов букв и подстрок.И в конце я проверяю все эти комбинации.Не очень эффективно, но работает.

public static int matches(String pattern, String example) {
    // 1. which pattern-letters exist?
    Set<String> set = new HashSet<>();
    for (int i = 0; i < pattern.length(); i++) {
        set.add(pattern.substring(i, i + 1));
    }

    // 2. which substrings of example exist?
    Set<String> substrings = new HashSet<>();
    for (int i = 0; i < (example.length() - 1); i++) {
        for (int j = i + 1; j < example.length(); j++) {
            substrings.add(example.substring(i, j));
        }
    }

    // 3. create all combinations
    List<Map<String, String>> list = new ArrayList<>();
    for (String s : set) {
        List<Map<String, String>> l = new ArrayList<>();
        for (String x : substrings) {
            if (list.isEmpty()) {
                Map<String, String> map = new HashMap<>();
                map.put(s, x);
                l.add(map);
            } else {
                for (Map<String, String> map : list) {
                    Map<String, String> map2 = new HashMap<>();
                    for (Entry<String, String> e : map.entrySet()) {
                        map2.put(e.getKey(), e.getValue());
                    }
                    map2.put(s, x);
                    l.add(map2);
                }
            }
        }
        list.addAll(l);
    }

    // 4. try all combinations
    for (Map<String, String> map : list) {
        String match = "";
        for (int i = 0; i < pattern.length(); i++) {
            match += map.get(pattern.substring(i, i + 1));
        }
        if (example.equals(match)) {
            return 1;
        }
    }

    return 0;
}

Answer 4

Вот мое решение.

public class App {
    public static void main(String args[]) {

        System.out.println(isMatch("abba","redbluebluered" ));
        System.out.println(isMatch("aaaa","asdasdasdasd" ));
        System.out.println(isMatch("aabb","xyzabcxzyabc" ));
    }

    static boolean isMatch(String patternString, String dataString) {
        List pattern = toList(patternString);
        List data = toList(dataString);

        return isMatch(pattern, data, new HashMap<>());
    }

    private static boolean isMatch(List pattern, List data, Map<Character, List> matches) {
        if (data == null) {
            return pattern == null;
        }

        if (matches.containsKey(pattern.c)) {
            List list = matches.get(pattern.c);
            List tmp = data;
            while (list != null) {
                if (tmp == null) {
                    return false;
                }
                if (list.c != tmp.c) {
                    return false;
                }
                tmp = tmp.next;
                list = list.next;
            }
            return isMatch(pattern.next, tmp, matches);
        }

        List tmp = data;
        List partialMatchHead;
        List partialMatchTail;
        partialMatchHead = new List();
        partialMatchHead.c = tmp.c;
        tmp = tmp.next;
        partialMatchTail = partialMatchHead;
        while (tmp != null) {
            Map<Character, List> map = new HashMap<>(matches);
            map.put(pattern.c, partialMatchHead);
            if (isMatch(pattern.next, tmp, map)) {
                return true;
            }
            partialMatchTail.next = new List();
            partialMatchTail.next.c = tmp.c;
            partialMatchTail = partialMatchTail.next;

            tmp = tmp.next;
        }
        return false;
    }


    private static List toList(String string) {
        List head = new List();
        head.c = string.charAt(0);
        List current = head;
        for (int i = 1; i < string.length(); i++) {
            List tmp = new List();
            tmp.c = string.charAt(i);
            current.next = tmp;
            current = tmp;
        }
        return head;
    }

    static class List {
        char c;
        List next;
    }
}

Это решение эквивалентно решению @Misha.

PS : здесь есть такой же вопрос в Python здесь

Answer 5

Это проще сделать рекурсивно.

На каждом шаге у нас есть шаблон для сопоставления слева, строка для сопоставления и сопоставление символа с строкой, которое мы уже присвоили:

// initially, map should be empty.  if this method returns true,
// map will contained the successful char-to-string mapping
boolean solve(String ptrn, String str, Map<Character, String> map) {
    // if pattern is empty, string must also be empty
    if (ptrn.length() == 0) {
        return str.length() == 0;
    }

    char c = ptrn.charAt(0);
    if (map.containsKey(c)) {
        // first char of the pattern is alrady assigned
        // the string must begin with the mapped substring
        String substitution = map.get(c);
        if (str.startsWith(substitution)) {
            // chop off the assigned substring and try to match the rest of the string
            return solve(ptrn.substring(1), str.substring(substitution.length()), map);
        } else {
            // the current assignment map is impossible.  fail!
            return false;
        }
    }

    // first char of the pattern is not assigned
    // loop over the string and try assigning substrings
    for (int i = 1; i <= str.length(); i++) {
        // assign new mapping and try to parse with the new assignment in place
        map.put(c, str.substring(0, i));
        if (solve(ptrn, str, map)) {
            return true;
        }
        // assignment failed.  remove it.
        map.remove(c);
    }
    return false;
}

Это, конечно, можно сделать более эффективным, работая с индексами вместо подстрок и заменяя некоторые рекурсии циклами.

Answer 6

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

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

В случае с «красно-голубым» эти блоки являются «красными» и «синими».

Set<String> findRepeatedStringsWithinString(String input) {
  Set<String> setOfStrings = new HashSet<String>();
  List<String> listOfStrings = new ArrayList<String>();
  for(int i = 0; i < input.length(); i++) {
    for(int j = 0; j < input.length() - i; j++) {
      String subString = input.substring(i,j);
      setOfStrings.add(subString);
      listOfStrings.add(subString);
    }
  }
  //At this point, I've got a Set of all unique substrings within the input and a List of all substrings that contains lots of duplicates.
  //I need to remove all of the unique Strings from the Set that don't have repeating values in the List for starters.
  //I'll end up with a Set that I think looks like this:
  // r, e, d, b, l, u, re, bl, ue, ed, red, blu, blue

  setOfStrings = removeAllUniqueStringsInListFromSet(listOfStrings, setOfStrings);

  //I've noticed that each of these units is as large as possible, so any String that is a subString within my Set seems valid to remove. I would confirm this with the interviewer.
  setOfString = removeSubStringsFromSet(setOfStrings);

  //Set = red, blue
  //From here, it's a matter of more String comparisons between this Set and the pattern, but other people are producing higher quality algorithms than mine and it's late. I don't think that continuing on this line of reasoning will get either of us the job, but I'll leave this here for others to compare.
}

Set<String> removeAllUniqueStringsInListFromSet(List<String> listOfStrings, Set<String> setOfStrings) {
Map<String, Integer> mapOfStrings = new HashMap<>();
  for(String possiblyUniqueString : listOfStrings) {
    if(mapOfStrings.get(possiblyUniqueString)) {
      mapOfStrings.put(possiblyUniqueString, mapOfStrings.get(possiblyUniqueString) + 1);
    } else {
      mapOfStrings.put(possiblyUniqueString, 1);
    }
  }
  //With this map of number of occurrences of each String in the List, I can now figure out which Strings are unique and remove them.
  for(String key : mapOfStrings.keySet()) {
    if(mapOfStrings.get(key) == 1) {
      setOfStrings.remove(key);
    }
  }
  return setOfStrings;
}

Set<String> removeSubStringsFromSet(Set<String> setOfStrings) {
  //This is me sucking at dealing with Sets, sorry
  List<String> listOfStrings = new ArrayList<>(setOfStrings);
  for(String string : listOfStrings) {
    for(int i = 0; i < listOfStrings.size(); i++) {
      if(!listOfStrings.get(i).equals(string) && listOfStrings.get(i).contains(string)) {
        setOfString.remove(string);
      }
    }
  }
  return setOfStrings;
}