https://leetcode.com/problems/unique-substrings-in-wraparound-string/
比较难想清楚的一道题，

个人解答

  1. class Solution:
  2.     def findSubstringInWraproundString(self, p: str) -> int:
  3.         if not p:
  4.             return 0
  6.         c = collections.defaultdict(int)
  7.         acc = 1
  8.         c[p[0]] = 1
  9.         valid = 'zabcdefghijklmnopqrstuvwxyz'
  10.         for i in range(1, len(p)):
  11.             if p[i - 1] + p[i] in valid:
  12.                 acc += 1
  13.             else:
  14.                 acc = 1
  16.             c[p[i]] = max(c[p[i]], acc)
  18.         return sum(c.values())

题目分析

题目描述的，很像一个数学问题，只要统计对应起始字符和结束字符的substring数量即可，然后再通过如果又更长的，必然出现重复，可以归约到短的substring上。
但是想了半天，想不出这样的解法。

discussion中大佬们给出的解法，的确是没想到，用这样的方式memorize，妙呀！

代码很短小。
基本思想包括：

  • 不重复的substring，那只要保证substring的结尾不同就好了
  • 相同结尾的substring有多少个呢？由于string的循环性，就是最长的substring的长度。有（结尾字符，长度）这两个，就可以唯一决定一个substring了

至于代码中判断是否是valid的substring，根据前后关系判断然后分段，这是比较容易想到的：

  1. if p[i - 1] + p[i] in valid:
  2.     acc += 1
  3. else:
  4.     acc = 1

妙在对这个最大程度的更新，看了解答发现如此自然，但是自己想却想不出这么优雅的方式。

可能，从思路到实际的实现，这其中，也是需要一定的积累和能力的。