2255. 統(tǒng)計是給定字符串前綴的字符串?dāng)?shù)目

方法一：雙指針

獲取word中每一個元素，遍歷該元素比對其與s的重合程度，若遍歷結(jié)束指針大小與該元素相等，則說明是前綴

該判斷方法將調(diào)用多次，至多一千次，因此封裝為函數(shù)

Python版本

C++版本

復(fù)雜度分析

• 時間復(fù)雜度： O(N)?？紤]到標(biāo)的字符串和比較字符串可以完全相同，那么比較次數(shù)可能為 words 數(shù)組長度與 s 串長度的乘積，即 1000 x 10 = 10000

• 空間復(fù)雜度：O(1)。

方法二：調(diào)用庫函數(shù)

Python 中 str 數(shù)據(jù)類型有此方法 str.startswith()可以幫助我們快速判斷前綴

Python版本

C++版本string.find()方法不穩(wěn)定，暫無

復(fù)雜度分析

• 時間復(fù)雜度：O(N)。僅考慮循環(huán)次數(shù)，此處的N指的是 words 數(shù)組的長度，上限為1000. 考慮到子字符最長為10，即常數(shù)C，總遍歷次數(shù)上限為10000，可看做復(fù)雜度為 N。

• 空間復(fù)雜度：O(1)。

備注

• 此題和884. 兩句話中的不常見單詞都使用了封裝，即把驗證每一個數(shù)據(jù)對象是否為前綴的部分代碼封裝為一個子函數(shù)，在C++中是以lambda函數(shù)的方式實現(xiàn)的。

• 這啟示我們對于代碼中相同的結(jié)構(gòu)盡量做出抽象，但同時注意到，函數(shù)形式比起匿名函數(shù)寬容度更高，即對數(shù)據(jù)的操作更加自由，而且語法層面不太容易出錯，一定要記得：匿名函數(shù)整體作為一句話代碼，其后一定有分號;