題目
給你兩個字符串 s 和 t，請找出 s 中的非空子串的數目，這些子串滿足替換一個不同字符以后，是 t 串的子串。換言之，請你找到 s 和 t 串中恰好只有一個字符不同的子字符串對的數目。
一個子字符串是一個字符串中連續的字符。
示例
示例 1
輸入：
s = "aba", t = "baba"
輸出：
6
解釋：
以下為只相差 1 個字符的 s 和 t 串的子字符串對：
- (“aba”, “baba”)
- (“aba”, “baba”)
- (“aba”, “baba”)
- (“aba”, “baba”)
- (“aba”, “baba”)
- (“aba”, “baba”)
示例 2
輸入：
s = "ab", t = "bb"
輸出：
3
解釋：
以下為只相差 1 個字符的 s 和 t 串的子字符串對：
- (“ab”, “bb”)
- (“ab”, “bb”)
- (“ab”, “bb”)
示例 3
輸入：
s = "a", t = "a"
輸出：
0
示例 4
輸入：
s = "abe", t = "bbc"
輸出：
10
提示
- 1 <=
s.length, t.length<= 100 s和t都只包含小寫英文字母。
代碼
#include <string.h>
#include <stdbool.h>
#include <stdio.h>
bool isOnlyOneDiff(const char* a,const char* b,int len)
{// printf("input %s,%s\n",a,b);int diffcnt = 0;for (int i = 0; i < len; i++){// printf("compare [%c, %c]\n",a[i], b[i]);if(a[i] == b[i]){continue;}diffcnt++;if(diffcnt > 1){return false;}}return (diffcnt == 1);
}int countSubstrings(char* s, char* t) {int len_s = strlen(s);int len_t = strlen(t);int res = 0;int smallerLen = (len_s <= len_t) ? len_s : len_t;int biggerLen = (len_s > len_t) ? len_s : len_t;char* smallerStr = (len_s <= len_t) ? s : t;char* biggerStr = (len_s > len_t) ? s : t;// 滿足題目呀求的子串長度一定相同，因此按照長度來遍歷for (int l = 0; l < smallerLen; l++){char* small = smallerStr;char* big = biggerStr;while (small + l * sizeof(char) < smallerStr + smallerLen * sizeof(char)){// printf("small while\n");while (big + l * sizeof(char) < biggerStr + biggerLen * sizeof(char)){// printf("big while\n");if(isOnlyOneDiff(small,big,l+1)){// printf("true\n");res++;}big += sizeof(char);}big = biggerStr;small += sizeof(char);}}return res;
}// int main(void)
// {
// char a[] = "ab";
// char b[] = "bb";
// int res = countSubstrings(a,b);
// printf("res = %d\n",res);
// }
解法思路
- 遍歷
s中的所有子串。 - 遍歷
t中的所有子串。 - 比較
s的子串和t的子串，檢查它們是否只有一個字符不同。 - 統計滿足條件的子字符串對的數量。
代碼思路分析
這個程序的目標是找出字符串 s 中的非空子串的數目，這些子串替換一個字符以后，可以成為字符串 t 的子串。具體思路如下：
-
函數
isOnlyOneDiff：- 檢查兩個相同長度的子串是否只有一個字符不同。
- 計數不同字符的數量，如果超過一個，返回
false。
-
函數
countSubstrings：- 獲取字符串
s和t的長度。 - 判斷
s和t中較短的那個字符串，并設定為smallerStr，另一個為biggerStr。 - 通過雙重循環，遍歷所有可能的子串組合，并利用
isOnlyOneDiff檢查每對子串是否只有一個字符不同。 - 統計滿足條件的子串對數目。
- 獲取字符串
分塊拆解分析
1. isOnlyOneDiff 函數
bool isOnlyOneDiff(const char* a, const char* b, int len) {int diffcnt = 0;for (int i = 0; i < len; i++) {if (a[i] != b[i]) {diffcnt++;if (diffcnt > 1) {return false;}}}return (diffcnt == 1);
}
- 輸入：兩個字符串子串
a和b及其長度len。 - 輸出：
true或false，表示兩個子串是否僅有一個字符不同。 - 邏輯：遍歷子串，計數不同字符數量，若超過一個字符不同則返回
false，否則返回是否恰好有一個字符不同。
2. countSubstrings 函數
int countSubstrings(char* s, char* t) {int len_s = strlen(s);int len_t = strlen(t);int res = 0;int smallerLen = (len_s <= len_t) ? len_s : len_t;int biggerLen = (len_s > len_t) ? len_s : len_t;char* smallerStr = (len_s <= len_t) ? s : t;char* biggerStr = (len_s > len_t) ? s : t;for (int l = 0; l < smallerLen; l++) {char* small = smallerStr;char* big = biggerStr;while (small + l * sizeof(char) < smallerStr + smallerLen * sizeof(char)) {while (big + l * sizeof(char) < biggerStr + biggerLen * sizeof(char)) {if (isOnlyOneDiff(small, big, l + 1)) {res++;}big += sizeof(char);}big = biggerStr;small += sizeof(char);}}return res;
}
- 輸入：兩個字符串
s和t。 - 輸出：滿足條件的子字符串對的數量
res。 - 邏輯：
- 獲取字符串長度。
- 確定較短的字符串為
smallerStr，較長的為biggerStr。 - 通過雙重循環遍歷所有可能的子串組合。
- 使用
isOnlyOneDiff函數檢查每對子串是否只有一個字符不同，并統計滿足條件的對子數量。
復雜度分析
時間復雜度
-
isOnlyOneDiff函數：- 時間復雜度為
O(l)，其中l是子串的長度。
- 時間復雜度為
-
countSubstrings函數：- 外層循環遍歷子串長度，最多為
O(n)次，其中n是較短字符串的長度。 - 內層雙重循環分別遍歷
smallerStr和biggerStr的子串，每次遍歷進行isOnlyOneDiff檢查。 - 綜上，時間復雜度為
O(n^3)，因為對于每個可能的子串長度l，內層循環總共最多執行O(n^2)次，每次比較需要O(l)時間。
- 外層循環遍歷子串長度，最多為
空間復雜度
- 主要使用了若干指針變量和計數變量，額外空間復雜度為
O(1)。
結果
總結
通過遍歷所有可能的子串組合，并利用輔助函數檢查每對子串是否只有一個字符不同，最終統計滿足條件的對子數量。算法時間復雜度較高為 O(n^3)，但對于題目限定的字符串長度范圍（<= 100）是可以接受的。
