c# - 在文本中查找匹配查询
问题描述
最近在面试时问了这个问题,我无法解决,所以需要一些建议我该如何解决这个问题
声明:我不能使用 REGEX 或任何内置库
***** 问题陈述如下*********
**matches 输入:文本(字符串),查询(字符串) 输出:如果你可以在文本中找到匹配的查询,则为 true,否则为 false 如果没有特殊字符,大多数语言都有一个 contains 方法可以做到这一点。一个特殊字符:'?' ——如果你找到“?” 在查询字符串中,它表示前一个字符是可选的(匹配 0 或 1 次)。
例子:
- 没有问号:
- 匹配(“你好世界”,“你好”)返回真
- 匹配(“你好世界”,“世界”)返回假
- 匹配(“你好世界”,“o W”)返回真
- match("hello World", "W o") 返回 false
- 匹配(“你好世界”,“h W”)返回假
- 带问号——“l?” 表示“可选 l”:
- 匹配(“heo World”,“hel?o”)返回真
- 匹配("helo World", "hel?o") 返回真 匹配("hello World", "hel?o") 返回假
- 确保您了解这种情况:
- match("hello World", "hell?lo") 返回真
- 你可以有多个问号:
- match("hello World", "ex?llo Worlds?") 返回 true
*****我的方法如下*********
public class StringPatternMatch
{
public static bool MatchPattern(string inputText, string pattern)
{
int count = 0; int patternIndex = 0;
for (var i = 0; i < inputText.Length; i++)
{
if (patternIndex > pattern.Length)
break;
if (inputText[i] == pattern[patternIndex] ||
(inputText[i] != pattern[patternIndex] && pattern[patternIndex + 1] == '?'))
count++;
patternIndex++;
}
return pattern.Length == count;
}
}
将两个字符串从一侧遍历到另一侧(例如从最右边的字符到最左边)。如果我们找到一个匹配的字符,我们会在两个字符串中继续前进,增加模式计数器 - 最后匹配计数与模式长度
我也提供了我的代码,但这并没有涵盖所有情况
当然下一轮我没有去,但我还在思考这个问题,还没有找到准确的解决方案——希望看到一些有趣的答案!
解决方案
您的想法可行,但您的实现过于简单:
// assumes the pattern is valid, e.g. no ??
public static boolean matches(String string, String pattern) {
int p = 0; // position in pattern
// because we only return boolean we can discard all optional characters at the beginning of the pattern
while (p + 1 < pattern.length() && pattern.charAt(p + 1) == '?')
p += 2;
if (p >= pattern.length())
return true;
for (int s = 0; s < string.length(); s++) // s is position in string
// find a valid start position for the first mandatory character in pattern and check if it matches
if (string.charAt(s) == pattern.charAt(p) && matches(string, pattern, s + 1, p + 1))
return true;
return false;
}
private static boolean matches(String string, String pattern, int s, int p) {
if (p >= pattern.length()) // end of pattern reached
return true;
if (s >= string.length() || string.charAt(s) != pattern.charAt(p)) // end of string or no match
// if the next character of the pattern is optional check if the rest matches
return p + 1 < pattern.length() && pattern.charAt(p + 1) == '?' && matches(string, pattern, s, p + 2);
// here we know the characters are matching
if (p + 1 < pattern.length() && pattern.charAt(p + 1) == '?') // if it is an optional character
// check if matching the optional character or skipping it leads to success
return matches(string, pattern, s + 1, p + 2) || matches(string, pattern, s, p + 2);
// the character wasn't optional (but matched as we know from above)
return matches(string, pattern, s + 1, p + 1);
}
推荐阅读
- javascript - 使用 localStorage 隐藏我的工具提示,但在我的脚本中
- android - 内核 (Android) 到用户空间消息多播错误:netlink_broadcast_filtered+0x24/0x3d4
- azure-logic-apps - 如何在 Azure 逻辑应用中使用 Azure Database for PostgreSQL?
- swift - 对计时器进行单元测试?
- c# - C# 反射 typeof(string).GetMethod("Equals) netcoreapp2.2 上的模糊匹配
- regex - 如何使用 htaccess 和正则表达式重定向 URL 的中间部分,使动态端保持原样?
- xml - 有没有办法在不使用 firebug 或 xpath 的情况下学习 xpath,因为 firefox 不支持插件?
- r - Plotly R 隐藏所有标签、刻度、图例等
- python - pyspark python数据框在不同功能中的重用
- node.js - 如何在弹性搜索查询中添加 AND OR?