每日記錄分析一個小算法
第一種實現(xiàn)方式
中心思想：不斷的去切割文本去匹配第一個符合條件的字符串
代碼如下
private static int strAppearInTextCount(String sourceStr, String findStr) {
int count = 0;
while (true) {
//獲取文本中第一個匹配的字符串的位置
int index = sourceStr.indexOf(findStr);
//index=-1代表沒有匹配到
if (index != -1) {
//每次都對sourceStr截取石窑，從上一次找到的字符串末尾位置開始截取
sourceStr = sourceStr.substring(index + findStr.length());
count++;
} else {
break;
}
}
return count;
}
時間復雜度：
假設文本出現(xiàn)的次數(shù)是m次炫欺，文本的長度是n，匹配的字符服串的長度是k揉抵，時間復雜度是O（m* n* k）亡容，其中n *k是indexof（）方法中消耗的時間復雜度咱們可以看下源碼如下
static int indexOf(String source,
String target,
int fromIndex) {
final int sourceLength = source.length();
final int targetLength = target.length();
if (fromIndex >= sourceLength) {
return (targetLength == 0 ? sourceLength : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetLength == 0) {
return fromIndex;
}
char first = target.charAt(0);
int max = (sourceLength - targetLength);
for (int i = fromIndex; i <= max; i++) {
/* Look for first character. */
if (source.charAt(i)!= first) {
while (++i <= max && source.charAt(i) != first);
}
/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetLength - 1;
for (int k = 1; j < end && source.charAt(j)
== target.charAt(k); j++, k++);
if (j == end) {
/* Found whole string. */
return i;
}
}
}
return -1;
}
可以看出java 源碼中匹配字符串是遍歷一個個字符查找的
空間復雜度：
假設文本出現(xiàn)的次數(shù)是m次，文本的長度是n冤今，匹配的字符服串的長度是k闺兢，每次文本截取的時候都會subString（）然后賦值，因為java字符串的不可變性戏罢，每次賦值都會重新申請一片內存屋谭〗拍遥空間復雜度是O（m）
第二種實現(xiàn)方式
中心思想：優(yōu)化字符串賦值導致消耗內存的問題，
可以利用indexof（）的重載方法桐磁，indexof（str悔耘，fromIndex）第二個參數(shù)是從該位置開始匹配字符串，每次更新這個參數(shù)即可
代碼如下
private static int strAppearInTextCount(String sourceStr, String findStr) {
int count = 0;
int index = 0;
while (true) {
//判斷是不是沒有符合條件的字符串了
if (index != -1) {
//每次更新下次要檢索的位置起點所意，它等于上一次匹配的字符串的結束位置
index = sourceStr.indexOf(findStr, index) + findStr.length();
count++;
} else {
break;
}
}
return count;
}
時間復雜度：O(m *n * k) 空間復雜度O(1)
