一般要找满足条件的substring或者substring的长度想法一般都是双指针，右指针每一次移动一个单位长度，然后左指针根据情况来决定如何移动。已此题为例，由于string的array里可能存在重复的string，所以首先我们需要一个basemap来记录每个string出现的最多次数，一个currmap来记录到目前为止在basemap里的元素那些出现了，出现了多少次，之后还需要一个count的变量来记录是不是string的array里面所有的元素都出现过了，因为有重复元素的话map的size不是array的长度。在这里右指针每次移动的单位步长是string array里string的长度step。根据右指针的移动分以下几种情况：
- 如果[right，right + step]的substring不在basemap中，left到right + step去，因为从left到right + step之前都不能满足要求
- 如果[right，right + step]的substring在basemap中，更新currmap和count之后，如果currmap对应的string出现不大于basemap中的值，看count是否等于string array的长度，等于的话加入结果集
- 如果[right，right + step]的substring在basemap中，更新currmap和count之后，如果currmap对应的string出现大于basemap中的值，左移left直到对应string在currmap的值等于basemap的值，看count是否等于string array的长度，等于的话加入结果集
注意为了不遗漏解，以上过程要从0 - step - 1开始的index全部进行一次，时间复杂度是O(n / step * step) == O(n)，线性时间复杂度，代码如下：
No comments:
Post a Comment