Проверьте, соответствует ли данная строка данному шаблону

Ответ 1

Вам просто не нужно переводить шаблон в regexp с использованием обратных ссылок, т.е. что-то вроде этого (Python 3 с загруженным модулем):

>>> print(re.match('(.+)(.+)\\2\\1', 'catdogdogcat'))
<_sre.SRE_Match object; span=(0, 12), match='catdogdogcat'>

>>> print(re.match('(.+)(.+)\\1\\2', 'redblueredblue'))
<_sre.SRE_Match object; span=(0, 14), match='redblueredblue'>

>>> print(re.match('(.+)(.+)\\2\\1', 'redblueredblue'))
None

Регулярное выражение выглядит довольно тривиально для генерации. Если вам нужно поддерживать более 9 backrefs, вы можете использовать именованные группы - см. документы regexp в Python.

Ответ 2

Самое простое решение, о котором я могу думать, состоит в том, чтобы разделить данную строку на четыре части и сравнить отдельные части. Вы не знаете, как долго a или b, но оба a имеют одинаковую длину, а также b. Таким образом, количество способов разделить данную строку не очень велико.

Пример: pattern = [a b a b], данная строка = redblueredblue (всего 14 символов)

• |a| (длина a) = 1, то это делает 2 символа для a и осталось 12 символов для b s, т.е. |b|= 6. Разделенная строка = r edblue r edblue. Эй, это соответствует сразу!
• (только из любопытства) |a| = 2, |b| = 5 → split string = re dblue re dblue → match

Пример 2: pattern = [a b a b], string = redbluebluered (всего 14 символов)

• |a| = 1, |b| = 6 → split string = r edblue b luered → no match
• |a| = 2, |b| = 5 → split string = re dblue bl uered → no match
• |a| = 3, |b| = 4 → split string = red blue blu ered → no match

Остальное не нужно проверять, потому что если вы переключили a на b и наоборот, ситуация будет идентичной.

Каков шаблон, который имеет [a b c a b c]?

Ответ 3

Вот решение для возврата назад. Ссылка источника.

public class Solution {

public boolean isMatch(String str, String pat) {
Map<Character, String> map = new HashMap<>();
return isMatch(str, 0, pat, 0, map);
 }

boolean isMatch(String str, int i, String pat, int j, Map<Character,  String> map) {
// base case
if (i == str.length() && j == pat.length()) return true;
if (i == str.length() || j == pat.length()) return false;

// get current pattern character
char c = pat.charAt(j);

// if the pattern character exists
if (map.containsKey(c)) {
  String s = map.get(c);

  // then check if we can use it to match str[i...i+s.length()]
  if (i + s.length() > str.length() || !str.substring(i, i + s.length()).equals(s)) {
    return false;
  }

  // if it can match, great, continue to match the rest
  return isMatch(str, i + s.length(), pat, j + 1, map);
}

// pattern character does not exist in the map
for (int k = i; k < str.length(); k++) {
  // create or update the map
  map.put(c, str.substring(i, k + 1));

  // continue to match the rest
  if (isMatch(str, k + 1, pat, j + 1, map)) {
    return true;
  }
}

// we've tried our best but still no luck
map.remove(c);

return false;
 }

}

Ответ 4

Еще одно решение рекурсии грубой силы:

import java.io.IOException;
import java.util.*;

public class Test {

    public static void main(String[] args) throws IOException {
        int res;
        res = wordpattern("abba", "redbluebluered");
        System.out.println("RESULT: " + res);
    }

    static int wordpattern(String pattern, String input) {
        int patternSize = 1;
        boolean res = findPattern(pattern, input, new HashMap<Character, String>(), patternSize);
        while (!res && patternSize < input.length())
        {
            patternSize++;
            res = findPattern(pattern, input, new HashMap<Character, String>(), patternSize);
        }
        return res ? 1 : 0;
    }

    private static boolean findPattern(String pattern, String input, Map<Character, String> charToValue, int patternSize) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (charToValue.containsKey(c)) {
                sb.append(charToValue.get(c));
            } else {
                // new character in pattern
                if (sb.length() + patternSize > input.length()) {
                    return false;
                } else {
                    String substring = input.substring(sb.length(), sb.length() + patternSize);
                    charToValue.put(c, substring);
                    int newPatternSize = 1;
                    boolean res = findPattern(pattern, input, new HashMap<>(charToValue), newPatternSize);
                    while (!res && newPatternSize + sb.length() + substring.length() < input.length() - 1) {
                        newPatternSize++;
                        res = findPattern(pattern, input, new HashMap<>(charToValue), newPatternSize);
                    }
                    return res;
                }
            }
        }
        return sb.toString().equals(input) && allValuesUniq(charToValue.values());
    }

    private static boolean allValuesUniq(Collection<String> values) {
        Set<String> set = new HashSet<>();
        for (String v : values) {
            if (!set.add(v)) {
                return false;
            }
        }
        return true;
    }
}

Ответ 5

Моя реализация на С#. Пытался искать что-то чистое в С#, не смог найти. Поэтому я добавлю его здесь.

   private static bool CheckIfStringFollowOrder(string text, string subString)
    {
        int subStringLength = subString.Length;

        if (text.Length < subStringLength) return false;

        char x, y;
        int indexX, indexY;

        for (int i=0; i < subStringLength -1; i++)
        {
            indexX = -1;
            indexY = -1;

            x = subString[i];
            y = subString[i + 1];

            indexX = text.LastIndexOf(x);
            indexY = text.IndexOf(y);

            if (y < x || indexX == -1 || indexY == -1)
                return false;
        }

        return true;

    }

Ответ 6

@EricM

Я тестировал ваше решение DFS, и оно кажется неправильным, например:

pattern = [ "a", "b", "a" ], s = "patrpatrr"

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

Моя идея состоит в том, чтобы предоставить дополнение dict (или объединить в этом dict) новое значение, чтобы отслеживать первый раз, когда он появляется, и другой стек, чтобы отслеживать уникальный образец, который я встречаю. когда "не совпадают", я буду знать, что есть проблема с последним шаблоном, и я выталкиваю его из стека и изменяю соответствующее значение в dict, также я снова начну проверять соответствующий индекс. Если нельзя изменить больше. Я буду появляться до тех пор, пока в стеке не останется ничего, а затем вернет False.

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

Ответ 7

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

Сложность во время выполнения O(n^(2m)), где m - длина шаблона, а n - длина строки.

Вот какой код для этого выглядит (я сделал свой код, вернув фактическое сопоставление вместо 0 или 1. Модификация кода для возврата 0 или 1 проста):

import java.util.Arrays;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class StringBijection {
    public static void main(String[] args) {
        String chars = "abaac";
        String string = "johnjohnnyjohnjohncodes";
        List<String> stringBijection = getStringBijection(chars, string);

        System.out.println(Arrays.toString(stringBijection.toArray()));
    }

    public static List<String> getStringBijection(String chars, String string) {
        if (chars == null || string == null) {
            return null;
        }

        Map<Character, String> bijection = new HashMap<Character, String>();
        Deque<String> assignments = new ArrayDeque<String>();
        List<String> results = new ArrayList<String>();
        boolean hasBijection = getStringBijection(chars, string, 0, 0, bijection, assignments);

        if (!hasBijection) {
            return null;
        }

        for (String result : assignments) {
            results.add(result);
        }

        return results;
    }

    private static boolean getStringBijection(String chars, String string, int charIndex, int stringIndex, Map<Character, String> bijection, Deque<String> assignments) {
        int charsLen = chars.length();
        int stringLen = string.length();

        if (charIndex == charsLen && stringIndex == stringLen) {
            return true;
        } else if (charIndex == charsLen || stringIndex == stringLen) {
            return false;
        }

        char currentChar = chars.charAt(charIndex);
        List<String> possibleWords = new ArrayList<String>();
        boolean charAlreadyAssigned = bijection.containsKey(currentChar);

        if (charAlreadyAssigned) {
            String word = bijection.get(currentChar);
            possibleWords.add(word);
        } else {
            StringBuilder word = new StringBuilder();

            for (int i = stringIndex; i < stringLen; ++i) {
                word.append(string.charAt(i));
                possibleWords.add(word.toString());
            }
        }

        for (String word : possibleWords) {
            int wordLen = word.length();
            int endIndex = stringIndex + wordLen;

            if (endIndex <= stringLen && string.substring(stringIndex, endIndex).equals(word)) {
                if (!charAlreadyAssigned) {
                    bijection.put(currentChar, word);
                }

                assignments.addLast(word);

                boolean done = getStringBijection(chars, string, charIndex + 1, stringIndex + wordLen, bijection, assignments);

                if (done) {
                    return true;
                }

                assignments.removeLast();

                if (!charAlreadyAssigned) {
                    bijection.remove(currentChar);
                }
            }
        }

        return false;
    }
}

Ответ 8

Если вы ищете решение на С++, это решение грубой силы: https://linzhongzl.wordpress.com/2014/11/04/repeating-pattern-match/

Ответ 9

Plain Brute Force, не уверен, что любая оптимизация возможна здесь.

import java.util.HashMap;
import java.util.Map;
import org.junit.*;

public class Pattern {
   private Map<Character, String> map;
   private boolean matchInt(String pattern, String str) {
      if (pattern.length() == 0) {
         return str.length() == 0;
      }
      char pch = pattern.charAt(0);
      for (int i = 0; i < str.length(); ++i) {
         if (!map.containsKey(pch)) {
            String val = str.substring(0, i + 1);
            map.put(pch, val);
            if (matchInt(pattern.substring(1), str.substring(val.length()))) {
               return true;
            } else {
               map.remove(pch);
            }
         } else {
            String val = map.get(pch);
            if (!str.startsWith(val)) {
               return false;
            }
            return matchInt(pattern.substring(1), str.substring(val.length()));
         }
      }
      return false;
   }
   public boolean match(String pattern, String str) {
      map = new HashMap<Character, String>();
      return matchInt(pattern, str);
   }
   @Test
   public void test1() {
      Assert.assertTrue(match("aabb", "ABABCDCD"));
      Assert.assertTrue(match("abba", "redbluebluered"));
      Assert.assertTrue(match("abba", "asdasdasdasd"));
      Assert.assertFalse(match("aabb", "xyzabcxzyabc"));
      Assert.assertTrue(match("abba", "catdogdogcat"));
      Assert.assertTrue(match("abab", "ryry"));
      Assert.assertFalse(match("abba", " redblueredblue"));
   }
}

Ответ 10

class StringPattern{
public:
  int n, pn;
  string str;
  unordered_map<string, pair<string, int>> um;
  vector<string> p;
  bool match(string pat, string str_) {
    p.clear();
    istringstream istr(pat);
    string x;
    while(istr>>x) p.push_back(x);
    pn=p.size();
    str=str_;
    n=str.size();
    um.clear();
    return dfs(0, 0);
  }

  bool dfs(int i, int c) {
    if(i>=n) {
      if(c>=pn){
          return 1;
      }
    }
    if(c>=pn) return 0;
    for(int len=1; i+len-1<n; len++) {
      string sub=str.substr(i, len);


      if(um.count(p[c]) && um[p[c]].fi!=sub
         || um.count(sub) && um[sub].fi!=p[c]
         )
          continue;
      //cout<<"str:"<<endl;
      //cout<<p[c]<<" "<<sub<<endl;
      um[p[c]].fi=sub;
      um[p[c]].se++;
      um[sub].fi=p[c];
      um[sub].se++;
      //um[sub]=p[c];
      if(dfs(i+len, c+1)) return 1;
      um[p[c]].se--;
      if(!um[p[c]].se) um.erase(p[c]);
      um[sub].se--;
      if(!um[sub].se) um.erase(sub);
      //um.erase(sub);
    }
    return 0;
  }
};

Мое решение, так как требуется двухсторонняя хэш-карта, а также нужно подсчитать количество отображений хеша

Ответ 11

Мое решение java script:

function isMatch(pattern, str){

  var map = {}; //store the pairs of pattern and strings

  function checkMatch(pattern, str) {

    if (pattern.length == 0 && str.length == 0){
      return true;
    }
    //if the pattern or the string is empty
    if (pattern.length == 0 || str.length == 0){
      return false;
    }

    //store the next pattern
    var currentPattern = pattern.charAt(0);

    if (currentPattern in map){
        //the pattern has alredy seen, check if there is a match with the string
        if (str.length >= map[currentPattern].length  && str.startsWith(map[currentPattern])){
          //there is a match, try all other posibilities
          return checkMatch(pattern.substring(1), str.substring(map[currentPattern].length));
        } else {
          //no match, return false
          return false;
        }
    }

    //the current pattern is new, try all the posibilities of current string
    for (var i=1; i <= str.length; i++){
        var stringToCheck = str.substring(0, i);

        //store in the map
        map[currentPattern] = stringToCheck;
        //try the rest
        var match = checkMatch(pattern.substring(1), str.substring(i));
        if (match){
            //there is a match
             return true;
        } else {
           //if there is no match, delete the pair from the map
           delete map[currentPattern];
        }
    }
    return false;
  }

  return checkMatch(pattern, str);

}

Ответ 12

В зависимости от того, какие шаблоны заданы, вы можете ответить на "другой" вопрос (это действительно тот же вопрос).

Для таких шаблонов, как [a b b a], определяется, является ли строка палиндром.

Для таких шаблонов, как [a b a b], определите, соответствует ли вторая половина строки первой половине строки.

Более длинные шаблоны, такие как [a b c b c a], но вы все равно разбиваете его на более мелкие проблемы. Для этого вы знаете, что последние n символов строки должны быть обратными к первым n символам. Как только они перестают быть равными, вам просто нужно проверить другую проблему [b c b c].

Хотя возможно, в интервью, я сомневаюсь, что они дадут вам что-нибудь более сложное, чем, возможно, 3-4 разных подстроки.