890. Find and Replace Pattern | Swift | July LeetCoding Challenge 2022

題目

2022/7/29 ，July LeetCoding Challenge 2022 的題目

• 題目： https://leetcode.com/problems/find-and-replace-pattern/
• 難度： Medium

思路

1. 先幫 pattern 做索引
2. 再幫 words 的每一個元素索引，有和 pattern 索引相符就加入回傳的陣列

資料結構

• 利用 HashMap (Dictionary) 做索引

程式碼

class Solution {
    func findAndReplacePattern(_ words: [String], _ pattern: String) -> [String] {
        let patternIndices = indices(pattern)
        return words.filter { indices($0) == patternIndices }
    }
    
    /// 傳入字串製作索引
    private func indices(_ word: String) -> [Int] {
        var indices = [Int]()
        var indexMap = [Character: Int]()
        var index = 0
        
        for character in word {
            if let current = indexMap[character]  {
                indices.append(current)
            } else {
                indexMap[character] = index
                indices.append(index)
                index += 1
            }
        }
        return indices
    }
}

Early Exist

有試著在 word 的途中碰到不同索引時就提早結束

但是可能是資料集的原因或是有判斷式反而運行速度沒有變快，

同時程式碼複雜度反而提升而變得不好閱讀，製作索引的程式碼也很難重用，在這邊就割愛不放了。

分析

• n - words 數量 + 1 (pattern)
• m - 每一個字串的長度

時間複雜度

O(n * m)

每一個字串的每一個字元都需要走訪一次

空間複雜度

O(n * m)

需要為每一個字串的每一個字元創建 hash map