LeetCode 1023 驼峰式匹配

LeetCode 1023 驼峰式匹配

给定一个模式字符串pattern和一组查询字符串queries,通过向pattern中插入小写字母来跟queries中的字符匹配。

Solution 1: Pattern Match

对于每一个要查询的字符串query的每一个字符q,当q是大写字母的时候,q必须匹配pattern中当前的大写字母,否则如果pattern已经遍历完了或者当前字符不能匹配q中的大写字母则当前字符串query的结果是false;当q是小写字母的时候,q如果能和pattern当前的小写字母匹配那么pattern的下标往后移,否则直接查询q的下一个字母。

  • 时间复杂度:O(m * n)
  • 空间复杂度:O(1)
class Solution {
public:
    vector<bool> camelMatch(vector<string> &queries, string &pattern) {
        vector<bool> ret;
        int n = pattern.size();
        for (auto &query:queries) {
            bool res = true;
            int i = 0;
            for (auto &q:query) {
                if (q < 'Z') {
                    if (i >= n || q != pattern[i]) {
                        res = false;
                        break;
                    }
                    ++i;
                } else if (q == pattern[i])
                    ++i;
            }
            ret.push_back(res && i == n);
        }
        return ret;
    }
};
class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        n, ret = len(pattern), []
        for query in queries:
            i, res = 0, True
            for q in query:
                if q <= 'Z':
                    if i >= n or q != pattern[i]:
                        res = False
                        break
                    i += 1
                elif i < n and q == pattern[i]:
                    i += 1
            ret.append(res and i == n)
        return ret
comments powered by Disqus