怎么把网站放到空间,网络营销的盈利模式,个人怎么建立网站,django个人博客网站开发部署源码给你两个字符串 word1 和 word2 。
如果一个字符串 x 重新排列后#xff0c;word2 是重排字符串的 前缀#xff0c;那么我们称字符串 x 是 合法的 。
请你返回 word1 中 合法 子字符串的数目。
示例 1#xff1a; 输入#xff1a;word1 bcca, word2 word2 是重排字符串的 前缀那么我们称字符串 x 是 合法的 。
请你返回 word1 中 合法 子字符串的数目。
示例 1 输入word1 bcca, word2 abc 输出1 解释 唯一合法的子字符串是 bcca 可以重新排列得到 abcc abc 是它的前缀。 示例 2 输入word1 abcabc, word2 abc 输出10 解释 除了长度为 1 和 2 的所有子字符串都是合法的。 示例 3 输入word1 abcabc, word2 aaabc 输出0 解释
1 word1.length 10^51 word2.length 10^4word1 和 word2 都只包含小写英文字母。
我的解答
class Solution {public long validSubstringCount(String word1, String word2) {int len1 word1.length(), len2 word2.length();// 记录word2中字母出现的次数int[] pre new int[26];// 记录word2中的字母在word1中出现的次数int[] p new int[26];for(char ch : word2.toCharArray()){pre[ch - a];}long res 0;int left 0;for(int i 0; i len1 ; i){int ch word1.charAt(i) - a;p[ch];if(pre[ch] 0 p[ch] pre[ch]) len2--;// 右遍历找到刚好包含word2中所有单词的子字符串后收拢左边区域if(len2 0){// 右边剩余单词可与当前字符串构成的组合long ans len1 - i;long count 0;while(left i){int left_ch word1.charAt(left) - a;count;left;// 左边单词为前缀单词,则该单词数减1if(pre[left_ch] 0){p[left_ch]--;// 如果当前单词数量减1后不符合前缀条件则退出循环进行向右补充单词if(p[left_ch] pre[left_ch]){len2;break;}}}res ans * count;}}return res;}
}
