Description 给定一个字符串 s,找出其中所有不含重复字符的子串,并将它们按照字典序排序后输出。 Format Input s = "abcabcbb" Output ['a', 'ab', 'abc', 'b', 'bc', 'bca', 'c', 'ca', 'cab', 'cb'] 解释:'abca'虽然为子串,含有重复字符,则不符合要求。 注意: 0 <= s.length <=10 s 仅由小写英文字母组成。 s 为空,则输出[]即可。
时间: 2023-10-23 16:39:38 浏览: 113
可以使用滑动窗口的方法来解决该问题。具体思路如下:
1. 定义一个滑动窗口,初始时左右指针都指向字符串的第一个字符。
2. 右指针不断向右移动,如果当前子串不含重复字符,则将该子串加入结果列表中。
3. 如果当前子串含有重复字符,则左指针向右移动,直到当前子串不再含有重复字符。
4. 重复步骤2和3,直到右指针到达字符串的末尾。
5. 对结果列表进行字典序排序,返回排序后的列表。
下面是使用 Python 代码实现该算法:
```python
def findSubstring(s: str) -> List[str]:
if not s:
return []
res = []
left, right = 0, 0
while right < len(s):
if s[right] not in s[left:right]:
res.append(s[left:right+1])
right += 1
else:
left += 1
return sorted(res)
```
该算法的时间复杂度为 $O(n^2)$,空间复杂度为 $O(n)$。
阅读全文