Недавно я был в интервью, и они задали мне следующий вопрос:
Напишите функцию для возврата true, если строка соответствует шаблону, false в противном случае
Образец: 1 символ на элемент, (a-z), ввод: строка с разделителями пространства
Это было мое решение для первой проблемы:
static boolean isMatch(String pattern, String input) {
char[] letters = pattern.toCharArray();
String[] split = input.split("\\s+");
if (letters.length != split.length) {
// early return - not possible to match if lengths aren't equal
return false;
}
Map<String, Character> map = new HashMap<>();
// aaaa test test test1 test1
boolean used[] = new boolean[26];
for (int i = 0; i < letters.length; i++) {
Character existing = map.get(split[i]);
if (existing == null) {
// put into map if not found yet
if (used[(int)(letters[i] - 'a')]) {
return false;
}
used[(int)(letters[i] - 'a')] = true;
map.put(split[i], letters[i]);
} else {
// doesn't match - return false
if (existing != letters[i]) {
return false;
}
}
}
return true;
}
public static void main(String[] argv) {
System.out.println(isMatch("aba", "blue green blue"));
System.out.println(isMatch("aba", "blue green green"));
}
Следующая часть проблемы остановила меня:
Без разделителей на входе написать одну и ту же функцию.
например:
isMatch("aba", "bluegreenblue") -> true
isMatch("abc","bluegreenyellow") -> true
isMatch("aba", "t1t2t1") -> true
isMatch("aba", "t1t1t1") -> false
isMatch("aba", "t1t11t1") -> true
isMatch("abab", "t1t2t1t2") -> true
isMatch("abcdefg", "ieqfkvu") -> true
isMatch("abcdefg", "bluegreenredyellowpurplesilvergold") -> true
isMatch("ababac", "bluegreenbluegreenbluewhite") -> true
isMatch("abdefghijklmnopqrstuvwxyz", "zyxwvutsrqponmlkjihgfedcba") -> true
Я написал решение bruteforce (генерируя все возможные расщепления входной строки размера letters.length и проверяя в свою очередь против isMatch), но интервьюер сказал, что это не оптимально.
Я понятия не имею, как решить эту часть проблемы, возможно ли это, или я что-то не хватает?
Они искали что-то со сложностью времени O(M x N ^ C), где M - длина шаблона, а N - длина ввода, C - некоторая константа.
Разъяснения
- Я не ищу регулярное выражение, даже если оно работает.
- Я не ищу наивное решение, которое генерирует все возможные расщепления и проверяет их даже при оптимизации, поскольку это всегда будет экспоненциальное время.
