題目資訊

• 題目編號: 2942
• 題目連結: Find Words Containing Character
• 主題: Array, String

題目敘述

您有一個從0開始索引的字串數組 words 和一個字元 x。

返回一個索引數組，代表包含字元 x 的單詞。

注意：返回的數組可以是任何順序。

範例 1：

輸入： words = [“leet”,“code”], x = “e”
輸出： [0,1]
解釋： “e” 出現在兩個單詞中：“leet” 和 “code"。因此，我們返回索引 0 和 1。

範例 2：

輸入： words = [“abc”,“bcd”,“aaaa”,“cbc”], x = “a”
輸出： [0,2]
解釋： “a” 出現在 “abc” 和 “aaaa” 中。因此，我們返回索引 0 和 2。

範例 3：

輸入： words = [“abc”,“bcd”,“aaaa”,“cbc”], x = “z”
輸出： []
解釋： “z” 沒有出現在任何單詞中。因此，我們返回一個空數組。

約束：

• $1 \leq \text{words.length} \leq 50$
• $1 \leq \text{words}[i].\text{length} \leq 50$
• $x$ 是一個小寫英文字母。
• $\text{words}[i]$ 僅由小寫英文字母組成。

直覺

此問題要求我們辨識出給定字串陣列中的哪些字串包含特定字符。這一任務自然導向使用迭代的方法來檢查每個字串是否含有目標字符。考慮到限制條件，直接了當的方法效率已經足夠，可以解決這個問題。

解法

這個解法採用了線性搜尋策略，檢視陣列中的每個字串以判斷其是否包含指定字符。下面是這個方法的逐步拆解：

1. 定義輔助函數：我們定義了一個私有輔助函數 containsCharacter，用於檢查特定字串中是否存在給予的字符。此函數逐一遍歷字串中的字符，若發現目標字符，則返回 true，否則返回 false。

2. 遍歷字串：在公共方法 findWordsContaining 中，我們初始化了一個空的向量 result，用於儲存包含目標字符的字串索引。

3. 檢查每個字串：使用索引 i 迭代遍歷字串列表。對每個字串，我們利用 containsCharacter 函數來確定字串是否包含指定字符 x。

4. 儲存索引：如果字串包含該字符，我們使用 emplace_back 將當前索引 i 附加到 result 向量中。

5. 返回結果：迴圈完成後，返回包含所有包含該字符的字串索引的 result 向量。

這個方法有效地遍歷所有字串並檢查字符，符合作業的時間複雜度為 $O(n \cdot m)$，其中 $n$ 是字串數量，$m$ 是字串的平均長度。考慮到問題的限制條件，這已經是相當有效的解法。

程式碼

C++

class Solution {
private:
    // 檢查字元 c 是否存在於字串 str 中
    bool containsCharacter(const string& str, char c) {
        for (char s : str) {
            if (s == c) {
                return true;
            }
        }
        return false;
    }
    
public:
    // 找出並返回包含字元 x 的單詞的索引
    vector<int> findWordsContaining(vector<string>& words, char x) {
        int len = words.size();
        vector<int> result;
        
        for (int i = 0; i < len; i++) {
            if (containsCharacter(words[i], x)) {
                result.emplace_back(i);
            }
        }
        
        return result;
    }
};

Python

class Solution:
    # 檢查字元 c 是否存在於字串 str 中
    def containsCharacter(self, str, c):
        for s in str:
            if s == c:
                return True
        return False

    # 找出並返回包含字元 x 的字的索引
    def findWordsContaining(self, words, x):
        len_words = len(words)
        result = []
        
        for i in range(len_words):
            if self.containsCharacter(words[i], x):
                result.append(i)
        
        return result

複雜度分析

• 時間複雜度: $O(n \cdot m)$
  時間複雜度是 $O(n \cdot m)$，其中 $n$ 是輸入陣列中的單詞數，$m$ 是單詞的最大長度。這是因為對於 words 陣列中的每個單詞，containsCharacter 函數會遍歷單詞中的每個字元來檢查字符 x 的存在。
• 空間複雜度: $O(n)$
  空間複雜度是 $O(n)$，其中 $n$ 是單詞的數量。這是由於 result 向量的存在，在最壞的情況下，如果所有單詞都包含字符 x，則可能存儲 words 陣列中每個單詞的索引。