leetcode 467. Unique Substrings in Wraparound String | 467. 环绕字符串中唯一的子字符串（动态规划）

小鱼儿 2022-09-08 11:53 112阅读 0赞

## 题目 ##

[https://leetcode.com/problems/unique-substrings-in-wraparound-string/][https_leetcode.com_problems_unique-substrings-in-wraparound-string]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5a-S5rOJSHE_size_5_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

##### 1、dp 超时版本 #####

class Solution { 
        public int findSubstringInWraproundString(String p) { 
            HashSet<Integer>[] arr = new HashSet[26]; // <结尾字母，长度>
            for (int i = 0; i < 26; i++) { 
                arr[i] = new HashSet();
            }
            
            arr[p.charAt(0) - 'a'].add(1);
            int curLen = 1; // 避免误将断链情况计入结果
            for (int i = 1; i < p.length(); i++) { 
                arr[p.charAt(i) - 'a'].add(1);
                if (p.charAt(i) == 'a' && p.charAt(i - 1) == 'z') { 
                    curLen++;
                    for (int len : arr[25]) { 
                        if (len + 1 <= curLen) arr[0].add(len + 1);
                    }
                } else if (p.charAt(i - 1) == p.charAt(i) - 1) { 
                    curLen++;
                    for (int len : arr[p.charAt(i - 1) - 'a']) { 
                        if (len + 1 <= curLen) arr[p.charAt(i) - 'a'].add(len + 1);
                    }
                } else { 
                    curLen = 1;
                }
            }
            
            int result = 0;
            for (int i = 0; i < 26; i++) { 
                result += arr[i].size();
            }
            return result;
        }
    }

##### 2、dp 答案版本 #####

参考：[Concise Java solution using DP][]

After failed with pure math solution and time out with DFS solution, I finally realized that this is a DP problem…  
The idea is, if we know the max number of unique substrings in `p` ends with `'a', 'b', ..., 'z'`, then the summary of them is the answer. Why is that?

1.  The max number of unique substring ends with a letter equals to the length of max contiguous substring ends with that letter. Example `"abcd"`, the max number of unique substring ends with `'d'` is 4, apparently they are `"abcd", "bcd", "cd" and "d"`.
2.  If there are overlapping, we only need to consider the longest one because it covers all the possible substrings. Example: `"abcdbcd"`, the max number of unique substring ends with `'d'` is 4 and all substrings formed by the 2nd `"bcd"` part are covered in the 4 substrings already.
3.  No matter how long is a contiguous substring in `p`, it is in `s` since `s` has infinite length.
4.  Now we know the max number of unique substrings in `p` ends with `'a', 'b', ..., 'z'` and those substrings are all in `s`. Summary is the answer, according to the question.

Hope I made myself clear…

class Solution { 
        public int findSubstringInWraproundString(String p) { 
            int[] dp = new int[26]; // <结尾字母，以当前字母结尾的最长串长度>
    
            dp[p.charAt(0) - 'a'] = 1;
            int curLen = 1;
            for (int i = 1; i < p.length(); i++) { 
                if (p.charAt(i - 1) == p.charAt(i) - 1 || p.charAt(i) == 'a' && p.charAt(i - 1) == 'z') { 
                    curLen++;
                } else { 
                    curLen = 1;
                }
                dp[p.charAt(i) - 'a'] = Math.max(dp[p.charAt(i) - 'a'], curLen);
            }
    
            int result = 0;
            for (int i = 0; i < 26; i++) { 
                result += dp[i];
            }
            return result;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5a-S5rOJSHE_size_7_color_FFFFFF_t_70_g_se_x_16]

[https_leetcode.com_problems_unique-substrings-in-wraparound-string]: https://leetcode.com/problems/unique-substrings-in-wraparound-string/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5a-S5rOJSHE_size_5_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/0ee5aba8df904b6f8f096f818482a56e.png
[Concise Java solution using DP]: https://leetcode.com/problems/unique-substrings-in-wraparound-string/discuss/95439/Concise-Java-solution-using-DP
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5a-S5rOJSHE_size_7_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/2db719bf00f745ae8a955118fbd47509.png