44. Wildcard Matching.txt

//Самый быстрый вариант.
//Код примерно работает так: Мы проверяем каждый символ строк s и p. Если символы равны или в строке p стоит знак ?, тогда символы считаются равными, переходим к следующим.
//Если в строке p стоит символ *,тогда чтобы символы совпали сохраняем индекс элемента строки p + 1 значение которого идёт после *. Так же сохраняем текущий индекс строки s. 
//	Переходим к следующему элементу строки p.(Ещё сохраняем индекс строки p, указывающего на последний элемент со знаком *).
//Если символы строк не совпадают, и при этом нет сохранённого индекса строки p, указывающего на последний элемент со знаком *, тогда возвращаем false.
//Если символы строк не совпадают, но при этом есть сохранённый индекс строки p, который указывает на последний элемент со знаком *, тогда строку p возвращаем назад к этому
//	индексу, а строку s, возвращаем на сохранённый индекс строки s + 1.
//Отдельно рассматриваем случай когда все элементы строки s рассмотрены, но в строке p ещё остались элементы. Если оставшиеся элементы не равны *, тогда возвращаем false.

bool isMatch(string s, string p) {
	//проведите этот пример на бумаге, если не можете понять, что делает решение: p = "a*bc" s = "abcbc".
	//sIdx - индекс элемента строки s, pIdx - индекс элемента строки p,
	int sIdx = 0, pIdx = 0, lastWildcardIdx = -1, sBacktrackIdx = -1, nextToWildcardIdx = -1;
	while (sIdx < s.size()) {//перебор всех символов строки s.
		//Если индекс строки p меньше размера строки p И (текущий элемент строки p равен ? 
			//ИЛИ текущий элемент строки p равен текущему элементу строки s).
		if (pIdx < p.size() && (p[pIdx] == '?' || p[pIdx] == s[sIdx])) {
			// совпадение символов
			++sIdx;//Увеличиваем индексы обоих строк для сравнения следующих символов.
			++pIdx;
		}
		//Если индекс строки p меньше размера строки p И текущий элемент строки p равен *
		else if (pIdx < p.size() && p[pIdx] == '*') {
			// подстановочный знак(*), чтобы символы совпадали - сохраняем индекс.
			lastWildcardIdx = pIdx;//Сохраняем индекс элемента * строки p
			nextToWildcardIdx = ++pIdx;//Сохраняем индекс на следующий элемент строки p после *, и переходим на него.
			sBacktrackIdx = sIdx;//Сохраняем индекс строки s, в котором элемент сравнивался со *.

			//сохраняем pidx+1, так как оттуда я хочу сопоставить оставшийся шаблон 
		}
		else if (lastWildcardIdx == -1) {
			// совпадений нет, и подстановочный знак не найден(*).
			return false;
		}
		else {
			// Если совпадений нет, но найден предыдущий подстановочный знак(*), тогда возвращаемся назад.
			pIdx = nextToWildcardIdx;//Возвращаемся к элементу строки p, стоящему после последнего знака *.
			sIdx = ++sBacktrackIdx;//Увеличиваем индекс для перехода на след. символ строки s, после последнего сравнивания s со *.
			//отслеживаем строку от предыдущего индекса backtrackidx + 1, чтобы посмотреть, есть ли в новом pidx и sidx одинаковые символы, 
	//если это так, значит, дикий символ может поглотить символы между собой, и далее мы можем запустить алгоритм, если на более 
	//позднем этапе он не работает, мы можем отступить.
		}
	}
	//Случай когда в строке p ещё остались элементы
	for (int i = pIdx; i < p.size(); i++) {
		if (p[i] != '*') return false;//false если они все неравны *.
	}
	return true;
	// true, если каждый оставшийся символ в p является подстановочным знаком
}



//Вот как должно было выглядеть моё решение в оптимальном варианте.
//Этот вопрос аналогичен вопросу 10. Сопоставление регулярных выражений , и оба вопроса можно решить с помощью динамического программирования.
//Во-первых, нам нужно создать 2D-таблицу dp. Размер этой таблицы (s.size() + 1) * (p.size() + 1). Мы вводим +1 здесь, чтобы лучше обрабатывать 
//	крайние случаи, когда у нас есть пустая строка или пустой шаблон. dp[i][j] означает, совпадает ли подстрока от индекса 0 до i - 1 исходной 
//	строки s с подшаблоном от индекса 0 до j - 1 исходного шаблона p.
//Далее мы инициализируем базовые случаи. Существует три базовых случая: 1) Когда и строка, и шаблон пусты: Всегда соответствовать dp[0][0] = true;
//	2) Когда только строка пуста: Только если подшаблон состоит только из *, у нас есть совпадение. 3) Когда только шаблон пуст: Всегда не совпадают.
//В шаблоне есть два специальных символа, которым нужно уделять особое внимание. 1) ?. На самом деле с этим легко справиться. Каждый раз, когда мы 
//	сталкиваемся с этим, мы можем считать, что оно соответствует любому символу в строке. Допустим, мы сейчас находимся в dp[i][j], и у нас 
//	есть p[j - 1] == '?', тогда мы знаем, что оно соответствует s[i - 1], независимо от того, что s[i - 1]на самом деле есть.
//	2) *. С этим немного сложно справиться. Небольшой прием при решении такого рода вопросов состоит в том, чтобы на самом деле нарисовать таблицу dp
//	и попытаться заполнить ее вручную, когда функция передачи состояния не очень проста. Все станет намного понятнее после того, как вы заполните 
//	одну-две строки. Когда мы встречаем a * в шаблоне и предполагаем, что в данный момент пытаемся выяснить, что это такое dp[i][j]. Тогда нам нужно
//	рассмотреть два случая, если p[j - 1] == '*'. A) Истина ли dp[i - 1][j]? Если да, это означает, что текущий подшаблон p[0...j - 1]соответствует 
//	подстроке s[0... i - 2]. Тогда будет p[0...j - 1]соответствовать s[0... i - 1]? Ответ — да, потому что * может соответствовать любой 
//	последовательности символов, а значит, может соответствовать еще одному символу s[i - 1]. 
//	B) Истина ли dp[i][j - 1]? Если да, это просто означает, что текущая подстрока s[0...i - 1]соответствует подшаблону p[0...j - 2]. Следовательно, 
//	если мы добавим еще один * в подшаблон, он также будет соответствовать * пустой подпоследовательности.


class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<bool>> dp(s.size() + 1, vector(p.size() + 1, false));
        dp[0][0] = true;
        for (int j = 0; j < p.size() && p[j] == '*'; ++j) {
            dp[0][j + 1] = true;
        }
        
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 1; j <= p.size(); ++j) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '?') && dp[i - 1][j - 1];
                }
            }
        }

        return dp[s.size()][p.size()];
    }
};



//Моё решение. Решал по принципу задачи 10 с помощью булевой матрицы (Динамическое програмирование).
class Solution {
public:
    bool isMatch(string s, string p) {
        int columns = s.size() + 1, rows = p.size() + 1;
        vector<vector<bool>> boolVect(columns, vector<bool>(rows));
        boolVect[0][0] = true;
        if (columns == 1) {
            for (int i = 1; i < rows; i++)
                if (p[i - 1] == '*')
                    boolVect[0][i] = boolVect[0][i - 1];
                else
                    boolVect[0][i] = false;
        }
        for (int i = 1; i < columns; i++) {
            for (int j = 1; j < rows; j++) {
                if (s[i - 1] == p[j - 1] || p[j - 1] == '?')
                    boolVect[i][j] = boolVect[i - 1][j - 1];
                else if (p[j - 1] == '*') {
                    boolVect[i][j] = boolVect[i - 1][j - 1] | boolVect[i - 1][j];
                    boolVect[i - 1][j] = boolVect[i][j];
                }
                else
                    boolVect[i][j] = false;
            }
        }
        if(rows > 2 && boolVect[columns - 1][rows - 1] == false && p[p.size() - 1] == '*'){
            int i = 1;
            while(p[p.size() - i] == '*') i++;
            boolVect[columns - 1][rows - 1] = boolVect[columns - 1][rows - 1] |
                boolVect[columns - 1][rows - i];
        }
        return boolVect[columns - 1][rows - 1];
    }
};