环绕字符串中的唯一子字符串
把字符串 s 看作是 "abcdefghijklmnopqrstuvwxyz" 的无限环绕字符串, 所以 s 看起来是这样的:"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
现在我们有了另一个字符串 p . 你需要的是找出 s 中有多少个唯一的 p 的非空子串, 尤其是当你的输入是字符串 p , 你需要输出字符串 s 中 p 的不同的非空子串的数目.
注意: p 仅由小写的英文字母组成, p 的大小可能超过 10000.
示例 1:
输入: "a"
输出: 1
解释: 字符串 S 中只有一个 "a" 子字符.
示例 2:
输入: "cac"
输出: 2
解释: 字符串 S 中的字符串 "cac" 只有两个子串 "a","c"..
示例 3:
输入: "zab"
输出: 6
解释: 在字符串 S 中有六个子串 "z","a","b","za","ab","zab"..
解题思想
这道题是说给了一个字符串 P, 需要从其中找到所有出现在 S 中的子串.
这里的 S 的子串是一个比较神奇的存在, 起就是 abcdedf..zabcde... 这样无限迭代下去的一个串, 也就是只要 P 的字符串一直递增就好 (z->a 进位)
所以解题方法也很直接:
找出以'a-z'每个字符结尾的情况下, 最长的子串有多长, 然后将其相加就可以
- public class Solution {
- /**
- * 其实就是找出 P 中有多少个子串, 子串能够在 abcdedf...zabcdefg...zab... 这样的一个子串里面找到
- * 也就是递增的过程
- * 考虑为一个 26 进制的数的序列
- * 使用 dp 的方式, 找到以某个字符结尾的最长的有多少种可能
- */
- public int findSubstringInWraproundString(String p){
- int p_int[] = new int[p.length()];
- int count[] = new int[26];
- for (int i = 0; i <p.length(); i++){
- p_int[i] = p.charAt(i) - 'a';
- }
- int res = 0;
- int maxLen = 0;
- for (int i = 0; i < p.length(); i++) {
- if (i> 0 && (p_int[i - 1] + 1) % 26 == p_int[i]) {
- maxLen++;
- } else {
- maxLen = 1;
- }
- count[p_int[i]] = Math.max(count[p_int[i]], maxLen);
- }
- for (int i = 0; i < 26; i++) res += count[i];
- return res;
- }
- }
来源: http://www.bubuko.com/infodetail-2923541.html