1023. Camelcase Matching

leetcode medium

#array#backtracking#csharp#leetcode#medium#string#two-pointers

Task

Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа.

Пример:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"

Output: [true,false,true,true,false]

C# solution

matched/original

public class Solution {
    public bool[] CamelMatch(string[] queries, string pattern) {
        bool Matches(string query, string pattern) {
            int i = 0, j = 0;
            while (i < query.Length) {
                if (j < pattern.Length && query[i] == pattern[j]) {
                    j++;
                } else if (char.IsUpper(query[i])) {
                    return false;
                }
                i++;
            }
            return j == pattern.Length;
        }
        
        bool[] answer = new bool[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            answer[i] = Matches(queries[i], pattern);
        }
        
        return answer;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool[] CamelMatch(vector<string> queries, string pattern) {
        bool Matches(string query, string pattern) {
            int i = 0, j = 0;
            while (i < query.size()) {
                if (j < pattern.size() && query[i] == pattern[j]) {
                    j++;
                } else if (char.IsUpper(query[i])) {
                    return false;
                }
                i++;
            }
            return j == pattern.size();
        }
        
        bool[] answer = new bool[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            answer[i] = Matches(queries[i], pattern);
        }
        
        return answer;
    }
}

Java solution

matched/original

public class Solution {
    public boolean[] camelMatch(String[] queries, String pattern) {
        boolean matches(String query, String pattern) {
            int i = 0, j = 0;
            while (i < query.length()) {
                if (j < pattern.length() && query.charAt(i) == pattern.charAt(j)) {
                    j++;
                } else if (Character.isUpperCase(query.charAt(i))) {
                    return false;
                }
                i++;
            }
            return j == pattern.length();
        }
        
        boolean[] answer = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            answer[i] = matches(queries[i], pattern);
        }
        
        return answer;
    }
}

JavaScript solution

matched/original

class Solution {
    camelMatch(queries, pattern) {
        const matches = (query, pattern) => {
            let i = 0, j = 0;
            while (i < query.length) {
                if (j < pattern.length && query[i] === pattern[j]) {
                    j++;
                } else if (query[i] >= 'A' && query[i] <= 'Z') {
                    return false;
                }
                i++;
            }
            return j === pattern.length;
        };
        
        return queries.map(query => matches(query, pattern));
    }
}

Python solution

matched/original

class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        def matches(query, pattern):
            i, j = 0, 0
            while i < len(query):
                if j < len(pattern) and query[i] == pattern[j]:
                    j += 1
                elif query[i].isupper():
                    return False
                i += 1
            return j == len(pattern)
        
        return [matches(query, pattern) for query in queries]

Go solution

matched/original

func camelMatch(queries []string, pattern string) []bool {
    matches := func(query, pattern string) bool {
        i, j := 0, 0
        
        for i < len(query) {
            if j < len(pattern) && query[i] == pattern[j] {
                j++
            } else if query[i] >= 'A' && query[i] <= 'Z' {
                return false
            }
            i++
        }
        
        return j == len(pattern)
    }
    
    answer := make([]bool, len(queries))
    for i, query := range queries {
        answer[i] = matches(query, pattern)
    }
    
    return answer
}

Explanation

Algorithm

Инициализация переменных:

Создайте массив answer для хранения результатов соответствия каждого запроса шаблону.

Проверка каждого запроса:

Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу.

Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса.

Возврат результата:

Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false.

Верните массив answer.

😎