leetcode

题目大意

  https://leetcode.com/problems/unique-substrings-in-wraparound-string

  字符串s可以认为“a……za……”的无限循环,给你一个字符串p,问p中有多少个子串也是s的子串

题目分析

  思路参考了这里https://discuss.leetcode.com/topic/70658/concise-java-solution-using-dp。动态规划,注意到字母个数一共就26个,想求总和,可以求以每个字符‘a’-‘z’结尾的字符串的个数(一定没有重复),求其总和即为所求。其实求以’a’-‘z’开头的也可以。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class {
private boolean check(String p, int idx) {
return (p.charAt(idx) + 1 == p.charAt(idx + 1)) || (p.charAt(idx) == 'z' && p.charAt(idx + 1) == 'a');
}
public int findSubstringInWraproundString(String p) {
if (p == null || p.length() == 0) {
return 0;
}
int len = p.length();
int[] longest = new int[26];
int max = 1;
for (int i = 0; i < len; i++) {
if (i > 0 && check(p, i - 1)) {
max++;
} else {
max = 1;
}
longest[p.charAt(i) - 'a'] = Math.max(longest[p.charAt(i) - 'a'], max);
}
int sum = 0;
for (int s : longest) {
sum += s;
}
return sum;
}
}

  算法复杂度:O(n) 空间复杂度:O(1)