Swift. Using two count arrays. Easy to understand.


  • 0
    M

    The idea is using two count array to store frequencies of characters in pattern p and the current window in string s. Run a loop from 0..<n-m, if the two array are identical, then found an anagram. Decrement the count of first character in the current windown. Increment the count of first character in the next window.
    We can do an optimization by only comparing the two arrays when the sum of unicode values of p and current window are the same.

    func findAnagrams(_ s: String, _ p: String) -> [Int] {
    // if length of s is smaller than p, then there is no anagram in s.
    let m = p.characters.count
    let n = s.characters.count
    var result = [Int]()
    if n < m {
        return result
    }
    // Initialize two count array for s and p.
    var sArray = Array(repeatElement(0, count: 256))
    var pArray = Array(repeatElement(0, count: 256))
    
    let sUnicodeArray = Array(s.unicodeScalars)
    let aValue = Int(UnicodeScalar("a")!.value)
    // store count of all character frequencies in p.
    for u in p.unicodeScalars {
        pArray[Int(u.value) - aValue] += 1
    }
    // store count of the first window character freqeuencies in s.
    for u in sUnicodeArray[0..<m] {
        sArray[Int(u.value) - aValue] += 1
    }
    // traverse characters in s from 0 to n-m-1
    for i in 0..<n-m {
        // if two array are idential, add the current i to result. Since two arrays are fixed size, it costs O(1) to compare two array.
        if sArray == pArray {
            result.append(i)
        }
        // decrement the count of first character in current window
        sArray[Int(sUnicodeArray[i].value) - aValue] -= 1
        // increment the count of first character in next window
        sArray[Int(sUnicodeArray[i+m].value) - aValue] += 1
    }
    // check for the last window
    if sArray == pArray {
        result.append(n-m)
    }
    return result
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.