leetcode
leetcode 951 ~ 1000
驼峰式匹配

驼峰式匹配

难度:

标签:

题目描述

代码结果

运行时间: 24 ms, 内存: 16.0 MB


/*
  思路: 
  使用 Java Stream API,我们可以通过流式处理查询列表,并检查每个查询字符串是否符合模式。
  我们将 matches 方法作为谓词,过滤出符合条件的查询。
*/
import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {
    public boolean[] camelMatch(String[] queries, String pattern) {
        return Arrays.stream(queries).map(query -> matches(query, pattern)).mapToBoolean(Boolean::booleanValue).toArray();
    }
    private boolean matches(String query, String pattern) {
        int pIndex = 0;
        for (char c : query.toCharArray()) {
            if (pIndex < pattern.length() && c == pattern.charAt(pIndex)) {
                pIndex++;
            } else if (Character.isUpperCase(c)) {
                return false;
            }
        }
        return pIndex == pattern.length();
    }
}

解释

方法:

这个题解使用了双指针的方法。我们同时遍历查询字符串 query 和模式字符串 pattern。对于 query 中的每个字符,如果它与 pattern 中的当前字符相匹配,我们就将两个指针都向前移动一位。如果它是小写字母,我们只移动 query 的指针。如果遇到一个大写字母且它与 pattern 中的当前字符不匹配,我们就直接返回 False。当我们完成遍历 query 时,我们检查 pattern 是否也被完全匹配了。

时间复杂度:

O(mn)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在匹配过程中遇到大写字母且不匹配时可以直接返回 False,而不进一步检查剩余的字符?
在驼峰式匹配中,大写字母是模式字符串中的关键字符,表示一个新的词的开始。如果在查询字符串中的大写字母与模式字符串中的当前字符不匹配,这表明模式字符串中的这部分词与查询字符串中的对应部分不同。因此,没有必要继续检查剩余字符,因为已经确定整体匹配失败。
🦆
在函数 `is_match` 中,为什么在处理完两个字符串的匹配后,还需要单独检查 query 中剩余的字符是否都为小写?
在处理完两个字符串的匹配后,可能还有部分字符在查询字符串 `query` 中剩余。如果这些剩余的字符中含有大写字母,则表示 `query` 中还有未被 `pattern` 包含的新词的开始,这违反了驼峰式匹配的规则,即 `pattern` 必须完全覆盖 `query` 中的所有词的开始。因此,需要确认剩余的所有字符都是小写字母,以确保匹配的有效性。
🦆
如果 `pattern` 字符串较长而 `query` 字符串较短,这种情况下的返回值是什么,逻辑是否已经在代码中得到正确处理?
如果 `pattern` 字符串较长而 `query` 字符串较短,意味着在 `query` 字符串遍历完毕后,`pattern` 中可能还有未匹配的字符。这种情况下,由于 `pattern` 的所有字符需要在 `query` 中找到对应的匹配字符,函数应该返回 `False`。在代码中,这种逻辑已经得到正确处理,即通过检查指针 `j` 是否等于 `pattern` 的长度来确认 `pattern` 是否完全被匹配。
🦆
这种双指针方法在处理所有大小写混合的字符串时是否总是有效?存在哪些可能的边界情况需要考虑?
双指针方法在处理大多数大小写混合字符串的驼峰式匹配问题时是有效的,但仍需考虑一些边界情况:1. `query` 或 `pattern` 为空字符串的情况;2. `query` 和 `pattern` 均只包含一个字符,且这个字符为大写或小写的情况;3. `query` 中包含连续的大写字母,而 `pattern` 不是这样的情况;4. `pattern` 中的字符完全不存在于 `query` 中的情况。这些情况需要通过适当的逻辑处理以确保函数的正确性和鲁棒性。

相关问题