LeetCode467. Unique Substrings in Wraparound String_综合

题目

Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:
Input: "a"
Output: 1Explanation: Only the substring "a" of string "a" is in the string s.
Example 2:
Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.
Example 3:
Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

分析

先大概说一下题意

字符串s可以看成是一个a-z围成的环儿，……xyzabc……，za相连。现在给你一个字符串p，让你找出字符串p中有多少个子字符串出现在s中。

大概思路就是找出它所有的连续子串，每个连续子串的结果相加，为最后的结果。

创建一个int数组pint，来存储字符串p中的字母，将字母转换成对应的数字：a-0，b-1，c-2,……z-25；

创建一个int数组count，用了记每个字母它的最大连续数。即abc：a的最大连续数位1，b为2，c为3；

count中所有数字相加，即为最后结果。

代码

class Solution {public int findSubstringInWraproundString(String p) {int[] pint = new int[p.length()];int[] count = new int[26];for (int i = 0; i < p.length(); i++)pint[i] = p.charAt(i)-'a';int re = 0;int max = 0;for (int i = 0; i < pint.length; i++) {if (i > 0 && ((pint[i] - pint[i-1]) == 1 || pint[i] == 0 && pint[i-1] == 25))max ++;else max = 1; count[pint[i]] = max;}for (int i = 0; i < 26; i++)re += count[i];return re;}
}