1.題目描述
把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的無限環(huán)繞字符串，所以 s 看起來是這樣的：
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." .
現(xiàn)在給定另一個字符串 p 尔崔。返回 s 中 唯一 的 p 的 非空子串 的數(shù)量 答毫。
示例 1:
輸入: p = "a"
輸出: 1
解釋: 字符串 s 中只有一個"a"子字符。
示例 2:
輸入: p = "cac"
輸出: 2
解釋: 字符串 s 中的字符串“cac”只有兩個子串“a”季春、“c”洗搂。.
示例 3:
輸入: p = "zab"
輸出: 6
解釋: 在字符串 s 中有六個子串“z”、“a”载弄、“b”耘拇、“za”、“ab”宇攻、“zab”惫叛。
2.思路
2.1 代碼
題目要求在字符串中找到連續(xù)子數(shù)組個數(shù)，其實(shí)就是在遍歷數(shù)組時尺碰，求以當(dāng)前字符結(jié)尾的連續(xù)子串長度挣棕，然后再把數(shù)組中每一位對應(yīng)的子串長度加起來求和便是最終答案。這里一下幾點(diǎn)需要注意：
- 重復(fù)字符的問題亲桥。出現(xiàn)重復(fù)字符時洛心，對比子串長度，以最長的為結(jié)果题篷，并最終結(jié)果只計(jì)算一次词身；
- 題目使用環(huán)形字符串，因此當(dāng)遍歷到 a 時番枚，如果前一位是 z 法严，那么就需要在前一位基礎(chǔ)上繼續(xù)往下算，即子串長度繼續(xù)加 1葫笼；
- 當(dāng)當(dāng)前位與前一位不連續(xù)時深啤，這個時候子串長度應(yīng)當(dāng)從 1 開始重新計(jì)算
以 “zab” 為例進(jìn)行說明：
- 遍歷 i=0 時，此時以 z 為結(jié)尾的連續(xù)子串只有 z 路星，因此統(tǒng)計(jì)個數(shù)為 1（z）溯街；
- 遍歷 i=1 時，此時以 a 為結(jié)尾的連續(xù)子串為 za洋丐，因?yàn)槭黔h(huán)形數(shù)組呈昔，所以 z 之后應(yīng)該繼續(xù)從 a 開始，此時統(tǒng)計(jì)個數(shù)為2（a友绝，za）堤尾；
- 遍歷 i=2 時，此時以 b為結(jié)尾的連續(xù)子串為 zab迁客，因此統(tǒng)計(jì)個數(shù)為3（b郭宝，ab辞槐，zab）；
- 最后將三個字符對應(yīng)的最長子串個數(shù)加起來等于 6 剩蟀，便是最終答案催蝗。
再以 “aabb” 為例說明存在重復(fù)字符時的處理過程：
- 遍歷 i=0 時，此時以 a 為結(jié)尾的連續(xù)子串只有 a 育特，因此統(tǒng)計(jì)個數(shù)為 1（a）丙号；
- 遍歷 i=1 時，此時以 a 為結(jié)尾的連續(xù)子串為 a缰冤，此時子串個數(shù)為 1 犬缨，但是因?yàn)榍懊娉霈F(xiàn)過 a ，兩個子串個數(shù)都是 1 棉浸，因此以 a 為結(jié)尾的連續(xù)子串個數(shù)為 1（a）怀薛；
- 遍歷 i=2 時，此時以 b為結(jié)尾的連續(xù)子串為 ab迷郑，因此統(tǒng)計(jì)個數(shù)為2（b枝恋，ab）；
- 遍歷 i=3 時嗡害，此時以 b 為結(jié)尾的連續(xù)子串為 b焚碌，長度為 1（b），但是前面出現(xiàn)過一次 b霸妹，因此選擇兩個子串中個數(shù)較大的作為以 b 結(jié)尾的子串十电，最終結(jié)果為 2；
- 遍歷完成得到最終答案是 3叹螟。
代碼中使用一 26 位的數(shù)組存放各個字符子串長度鹃骂，count 統(tǒng)計(jì)子串長度，當(dāng)不連續(xù)時罢绽，count 重置為 1畏线，代碼如下：
class Solution {
public int findSubstringInWraproundString(String p) {
char[] chars = p.toCharArray();
int[] tmp = new int[26];
tmp[chars[0] - 'a'] = 1;
int count = 1;
for (int i = 1; i < chars.length; i++) {
if (chars[i] == chars[i - 1] + 1 || (chars[i] == 'a' && chars[i - 1] == 'z')) {
count++;
} else {
count = 1;
}
tmp[chars[i] - 'a'] = Math.max(count, tmp[chars[i] - 'a']);
}
int ans = 0;
for (int i = 0; i < 26; i++) {
ans += tmp[i];
}
return ans;
}
}
2.2 測試結(jié)果
通過測試
測試結(jié)果
3.總結(jié)
- 題目轉(zhuǎn)換為求以字符結(jié)尾的連續(xù)子串長度更容易解答
- 使用 tmp 數(shù)組統(tǒng)計(jì)每一位字符為結(jié)尾的連續(xù)子數(shù)組個數(shù)
- 當(dāng)存在不連續(xù)的時候，count 重置為 1
- 這道題其實(shí)挺難的良价，主要很容易陷入慣性思維寝殴，從頭開始往后迭代進(jìn)行字符判斷，但是一旦把思維轉(zhuǎn)換過來后所有問題都迎刃而解了
