leetcode-unique-substrings-in-wraparoud-string

题目大意

　　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’开头的也可以。

代码

public class Solution {
    
    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)