通配符模式匹配：

Question

通配符模式匹配:给定一个字符串和一个包含通配符的模式，即*和?，其中?可以匹配输入字符串中的任何单个字符，而*可以匹配任意数量的字符(包括零字符)，设计一种有效的算法来查找该模式是否与完整的输入字符串匹配。

例如：

• 输入：string = "xyxzzxy"，=“x*y” 输出：匹配
• 输入：string = "xyxzzxy"，=“x*x” 输出：不匹配
• 输入：String = "xyxzzxy"，=“x*x？” 输出：匹配
• 输入：String = "xyxzzxy"，= "*“ 输出：匹配

Answer 1

在基础类(特别是NSPredicate)的帮助下，您可以简单地实现通配符匹配

func wildcard(_ string: String, pattern: String) -> Bool {
    let pred = NSPredicate(format: "self LIKE %@", pattern)
    return !NSArray(object: string).filtered(using: pred).isEmpty
}

喜欢比较完全符合您的要求：

左手表达式等于右手表达式：？和*允许作为通配符字符，在哪里？匹配1个字符和*匹配0或多个字符。

示例：

print(wildcard("xyxzzxy", pattern: "x***y"))  // true
print(wildcard("xyxzzxy", pattern: "x***x"))  // false
print(wildcard("xyxzzxy", pattern: "x***x?")) // true
print(wildcard("xyxzzxy", pattern: "*"))      // true

print(wildcard("a12b34c", pattern: "a?b?c"))      // false
print(wildcard("a12b34c", pattern: "a*b*c"))      // true

Answer 2

如果问题是“设计一个有效的算法.”，您可以这样定义字符串的扩展：

extension String {
    func matches(wildcard pattern: String) -> Bool {
        var strIndex = self.startIndex, matchIndex = self.startIndex
        var patternIndex = pattern.startIndex, asteriskIndex = pattern.endIndex

        while strIndex < self.endIndex {
            //Characters match, or question mark
            if patternIndex < pattern.endIndex
                && (self[strIndex] == pattern[patternIndex] || pattern[patternIndex] == "?") {
                strIndex = self.index(after: strIndex)
                patternIndex = pattern.index(after: patternIndex)
            }
            //Asterisk character
            else if patternIndex < pattern.endIndex && pattern[patternIndex] == "*" {
                asteriskIndex = patternIndex
                matchIndex = strIndex
                patternIndex = pattern.index(after: patternIndex)
            }
            else if asteriskIndex != pattern.endIndex {
                patternIndex = pattern.index(after: asteriskIndex)
                matchIndex = self.index(after: matchIndex)
                strIndex = matchIndex
            }
            else { return false }
        }

        //Asterisk character at the end of the pattern
        while patternIndex < pattern.endIndex && pattern[patternIndex] == "*" {
            patternIndex = pattern.index(after: patternIndex)
        }

        return patternIndex == pattern.endIndex
    }
}

这是一个更具可读性的这代码版本。

下面是一些测试用例：

"xyxzzxy".matches(wildcard: "x***y")      //true
"xyxzzxy".matches(wildcard: "x***x")      //false
"xyxzzxy".matches(wildcard: "x***x?")     //true
"xyxzzxy".matches(wildcard: "*")          //true

Answer 3

让Martin的解决方案更进一步，下面是一个接受模式并返回所有匹配元素的[String]扩展：

extension Array where Element == String {
    func wildcard(pattern: String) -> [String] {
        var returnArray: [String] = []
        
        for item in self {
            if (wildcard(item, pattern: pattern)) {
                returnArray.append(item)
            }
        }
        
        return returnArray
    }
    
    // Credit to Martin R @ SO for this brilliance: https://stackoverflow.com/a/57271935/215950
    private func wildcard(_ string: String, pattern: String) -> Bool {
        let pred = NSPredicate(format: "self LIKE %@", pattern)
        return !NSArray(object: string).filtered(using: pred).isEmpty
    }
}