驼峰式匹配
难度:
标签:
题目描述
代码结果
运行时间: 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 中剩余的字符是否都为小写?
▷🦆
如果 `pattern` 字符串较长而 `query` 字符串较短,这种情况下的返回值是什么,逻辑是否已经在代码中得到正确处理?
▷🦆
这种双指针方法在处理所有大小写混合的字符串时是否总是有效?存在哪些可能的边界情况需要考虑?
▷