这个问题最近在面试中被问到,我无法解决,所以需要一些建议,我该如何解决这个问题
声明:我不能使用 REGEX 或任何内置库
*****问题陈述如下*********
**匹配 输入:文本(字符串)、查询(字符串) 输出:如果可以在文本中找到查询的匹配项,则为 true,否则为 false 如果没有特殊字符,大多数语言都有一个 contains 方法可以做到这一点。 一个特殊字符:'?' -- 如果你发现 '?'在查询字符串中,它表示前一个字符是可选的(匹配 0 次或 1 次)。
例子:
- 没有问号:
- matches("hello World", "hello") 返回真
- matches("hello World", "world") 返回 false
- 匹配(“hello World”,“o W”)返回真
- matches("hello World", "W o") 返回 false
- matches("hello World", "h W") 返回 false
- 带问号——“l?”表示“可选 l”:
- matches("heo World", "hel?o") 返回真值
- matches("helo World", "hel?o") 返回真 matches("hello World", "hel?o") 返回 false
- 确保你理解这个案例:
- matches("hello World", "hell?lo") 返回真值
- 你可以有多个问号:
- matches("hello World", "ex?llo Worlds?") 返回真值
***** 我的方法如下*********
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);
}
关于c# - 在文本中查找查询匹配项,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55770224/