Wildcard Pattern Matching:

Question

Wildcard Pattern Matching: Given a string and a pattern containing wildcard characters i.e. * and ?, where ? can match to any single character in the input string and * can match to any number of characters including zero characters, design an efficient algorithm to find if the pattern matches with the complete input string or not.

For example:

• Input: string = "xyxzzxy", pattern = "x***y"

  Output: Match

• Input: string = "xyxzzxy", pattern = "x***x"

  Output: No Match

• Input: String = "xyxzzxy", pattern = "x***x?"

  Output: Match

• Input: String = "xyxzzxy", pattern = "*"

  Output: Match

Answer 1

With the help of Foundation classes (in particular NSPredicate) you can implement wildcard matching simply as

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

The LIKE comparison does exactly what you want:

The left hand expression equals the right-hand expression: ? and * are allowed as wildcard characters, where ? matches 1 character and * matches 0 or more characters.

Examples:

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

If the question is to "design an efficient algorithm...", you could define an extension on String this way:

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
    }
}

It is a more readable version of this code.

Here are some test cases:

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

Answer 3

Taking Martin's solution a step further, here's a [String] extension that will accept a pattern and return all matching elements:

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
    }
}

Answer 4

func matchingString() {

    var savingValueOfJ = 0
    var boolean = [Bool]()
    inputString =  inputStringTextField.text!
    pattern = patternTextField.text!

    let inputCharacters = Array(inputString)
    let patternCharacters = Array(pattern)
    for (index, firstCharacter) in patternCharacters.enumerated()    {
        if index == patternCharacters.count - 1, index != 0 {
            if inputCharacters.last == firstCharacter || firstCharacter == "*" || firstCharacter == "?"  {
                boolean.append(true)
                break
            }
            else {
                boolean.append(false)
                break
            }
        } else {
            if firstCharacter != "*" {
                while savingValueOfJ  <= inputCharacters.count {
                    if firstCharacter == inputCharacters[savingValueOfJ] || firstCharacter == "?" {

                        boolean.append(true)
                        savingValueOfJ += 1
                        break
                    } else {

                        boolean.append(false)
                        savingValueOfJ += 1
                        break
                    }

                }

            }
        }
    }

    let arr = boolean.filter{ $0 == false}
    if arr.count > 0 {
        displayingResultLbl.text = "Not A Match"
    }
    else {
        displayingResultLbl.text = "Matche's"
    }
}