string - problems - Compruebe si la cadena dada sigue el patrón dado
dynamic programming problems (14)
Un amigo mío acaba de tener su entrevista en Google y fue rechazado porque no podía dar una solución a esta pregunta.
Tengo mi propia entrevista en un par de días y parece que no puedo encontrar una manera de resolverlo.
Aquí está la pregunta:
Te dan un patrón, como [abab]. También te dan una cadena, ejemplo "redblueredblue". Necesito escribir un programa que diga si la cadena sigue el patrón dado o no.
Algunos ejemplos:
Patrón: [abba] Cadena: catdogdogcat devuelve 1
Patrón: [abab] Cadena: redblueredblue devuelve 1
Patrón: [abba] Cadena: redblueredblue devuelve 0
Pensé en algunos enfoques, como obtener el número de caracteres únicos en el patrón y luego encontrar muchas subcadenas únicas de la cadena y compararlas con el patrón mediante un hashmap. Sin embargo, eso resulta ser un problema si la subcadena de a es parte de b.
Sería realmente genial si alguno de ustedes pudiera ayudarme con eso. :)
ACTUALIZAR:
Información agregada: Puede haber cualquier número de caracteres en el patrón (az). Dos caracteres no representarán la misma subcadena. Además, un personaje no puede representar una cadena vacía.
Mi solución de script java:
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);
}
@EricM
Probé tu solución DFS y me parece mal, como en el caso:
patrón = ["a", "b", "a"], s = "patrpatrr"
El problema es que cuando cumple con un patrón que ya existe en dict y encuentra que no se ajusta a la siguiente cadena, borra e intenta asignarle un nuevo valor. Sin embargo, no ha comprobado este patrón con el nuevo valor para los tiempos anteriores en que ocurre.
Mi idea es proporcionar un nuevo valor de adición (o combinación en este dict) para realizar un seguimiento de la primera vez que aparece y otra pila para realizar un seguimiento del patrón único que encuentro. cuando ocurra "no coincidencia", sabré que hay algún problema con el último patrón y lo saco de la pila y modifico el valor correspondiente en el dict, también comenzaré a verificar nuevamente ese índice correspondiente. Si no se puede modificar más. Voy a hacer estallar hasta que no quede nada en la pila y luego devolveré False.
(Quiero agregar comentarios, pero no tengo suficiente reputación como nuevo usuario ... No lo he implementado, pero hasta ahora no he encontrado ningún error en mi lógica. Lo siento si hay algún problema con mi solución. == Intentaré implementarlo más tarde.)
Aquí está la solución de backtracking java. Fuente de enlace .
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;
}
}
Dependiendo de los patrones que se den, puede responder una pregunta ''diferente'' (esa es realmente la misma pregunta).
Para patrones como [abba], determine si la cadena es un palíndromo o no.
Para patrones como [abab] determina si la segunda mitad de la cadena es igual a la primera mitad de la cadena.
Patrones más largos como [abcbca], pero aún así puedes dividirlo en problemas más pequeños para resolver. Para este, sabes que los últimos n caracteres de la cadena deben ser el reverso de los primeros n caracteres. Una vez que dejan de ser iguales, simplemente tienes que buscar otro problema [bcbc].
Aunque es posible, en una entrevista, dudo que te den algo más complejo que quizás 3-4 subcadenas diferentes.
Fuerza bruta simple, no estoy seguro de si es posible alguna optimización aquí ...
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"));
}
}
La solución más simple en la que puedo pensar es dividir la cadena dada en cuatro partes y comparar las partes individuales. No sabe cuánto tiempo es a o b , pero tanto a s son de la misma longitud como b s. Así que el número de maneras de dividir la cadena dada no es muy grande.
Ejemplo: patrón = [abab] , cadena dada = redblueredblue (14 caracteres en total)
-
|a|(longitud dea) = 1, entonces eso hace 2 caracteres paraasy 12 caracteres parabs, es decir|b|= 6. Cadena dividida =r edblue r edblue. Whoa, esto coincide de inmediato! - (solo por curiosidad)
|a| = 2, |b| = 5|a| = 2, |b| = 5|a| = 2, |b| = 5-> cadena dividida =re dblue re dblue-> match
Ejemplo 2: patrón = [abab] , cadena = redbluebluered (14 caracteres en total)
-
|a| = 1, |b| = 6|a| = 1, |b| = 6-> cadena dividida =r edblue b luered-> no coincide -
|a| = 2, |b| = 5|a| = 2, |b| = 5-> cadena dividida =re dblue bl uered-> no coincide -
|a| = 3, |b| = 4|a| = 3, |b| = 4-> cadena dividida =red blue blu ered-> no coincide
No es necesario revisar el resto porque si cambia a por b y viceversa, la situación es idéntica.
¿Cuál es el patrón que tiene [abcabc]?
Mi implementación en C #. Intenté buscar algo limpio en C #, no pude encontrarlo. Así que lo añadiré aquí.
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;
}
No puedo pensar en una solución mucho mejor que la fuerza bruta: intente cada posible división de la palabra (esto es esencialmente lo que Jan describió).
La complejidad del tiempo de ejecución es O(n^(2m)) donde m es la longitud del patrón n es la longitud de la cadena.
Así es como se ve el código (hice que mi código devolviera la asignación real en lugar de solo 0 o 1. Modificar el código para devolver 0 o 1 es fácil):
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;
}
}
No solo necesita traducir el patrón a una expresión regular utilizando referencias inversas, es decir, algo como esto (Python 3 con el módulo "re" cargado):
>>> 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
La expresión regular parece bastante trivial para generar. Si necesita admitir más de 9 backrefs, puede usar grupos con nombre - vea la sección de expresiones regulares de Python .
Resolví esto como un problema de producción de lenguaje usando regexen.
def wordpattern( pattern, string):
''''''
input: pattern ''abba''
string ''redbluebluered''
output: 1 for match, 2 for no match
''''''
# assemble regex into something like this for ''abba'':
# ''^(?P<A>.+)(?P<B>.+)(?P=B)(?P=A)$''
p = pattern
for c in pattern:
C = c.upper()
p = p.replace(c,"(?P<{0}>.+)".format(C),1)
p = p.replace(c,"(?P={0})".format(C),len(pattern))
p = ''^'' + p + ''$''
# check for a preliminary match
if re.search(p,string):
rem = re.match(p,string)
seen = {}
# check to ensure that no points in the pattern share the same match
for c in pattern:
s = rem.group(c.upper())
# has match been seen? yes, fail, no continue
if s in seen and seen[s] != c:
return 0
seen[s] = c
# success
return 1
# did not hit the search, fail
return 0
Si está buscando una solución en C ++, aquí hay una solución de fuerza bruta: https://linzhongzl.wordpress.com/2014/11/04/repeating-pattern-match/
Una solución más de recursión de fuerza bruta:
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;
}
}
pattern - "abba"; input - "redbluebluered"
- Encuentra recuentos para cada carácter único en
pattern, asigna a la listapattern_countEj .:[2,2]paraayb. - Asigne
pattern_lengthspara cada carácter único. Ej .:[1,1]. - Iterar los valores de
pattern_lengthsdepattern_lengthsderecha a izquierda:pattern_count * (pattern_lengths)^T = length(input)(productopattern_count * (pattern_lengths)^T = length(input)de vectores). Utilice el paso para saltar directamente a la raíz de la siguiente ecuación. - Cuando se mantiene la ecuación, verifique si la cadena sigue patrones con los actuales
pattern_lenghts(check_combination())
Implementación de Python:
def check(pattern, input):
def _unique(pattern):
hmap = {}
for i in pattern:
if i not in hmap:
hmap[i] = 1
else:
hmap[i] += 1
return hmap.keys(), hmap.values()
def check_combination(pattern, string, pattern_unique, pattern_lengths):
pos = 0
hmap = {}
_set = set()
for code in pattern:
string_value = string[pos:pos + pattern_lengths[pattern_unique.index(code)]]
if code in hmap:
if hmap[code] != string_value:
return False
else:
if string_value in _set:
return False
_set.add(string_value)
hmap[code] = string_value
pos += len(string_value)
return False if pos < len(string) else True
pattern = list(pattern)
pattern_unique, pattern_count = _unique(pattern)
pattern_lengths = [1] * len(pattern_unique)
x_len = len(pattern_unique)
i = x_len - 1
while i>0:
diff_sum_pattern = len(input) - sum([x * y for x, y in zip(pattern_lengths, pattern_count)])
if diff_sum_pattern >= 0:
if diff_sum_pattern == 0 and /
check_combination(pattern, input, pattern_unique, pattern_lengths):
return 1
pattern_lengths[i] += max(1, diff_sum_pattern // pattern_count[i])
else:
pattern_lengths[i:x_len] = [1] * (x_len - i)
pattern_lengths[i - 1] += 1
sum_pattern = sum([x * y for x, y in zip(pattern_lengths, pattern_count)])
if sum_pattern <= len(input):
i = x_len - 1
else:
i -= 1
continue
return 0
task = ("abcdddcbaaabcdddcbaa","redbluegreenyellowyellowyellowgreenblueredredredbluegreenyellowyellowyellowgreenblueredred")
print(check(*task))
En el patrón de muestra de este código (20 caracteres, 4 únicos) funciona 50000 veces más rápido que la fuerza bruta simple (DFS) con recursión (implementación por @EricM); 30 veces más rápido que la expresión regular (implementación por @IknoweD).
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;
}
};
Mi solución, ya que se necesita un hashmap de dos lados, y también debo contar los conteos del mapa de hash