Who's Studio.

hihoCoder#1152 - Lucky Substrings

Word count: 261Reading time: 1 min
2016/05/10

题目

如果一个字符串的所有不同字符数量是一个斐波那契数，那它就是一个Lucky String。给定一个仅包含小写字母的字符串，按字典序输出其所有非空的Lucky Subtring。
具体描述请见hihoCoder。

解题思路

暴力搜索。

时间复杂度

遍历一遍字符串，对每个字符又要进行一次遍历，时间复杂度为N2。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <vector>
using namespace std;

set<string> luckySubstr(string str) {
	set<string> substrs;
	int fib[] = { 1, 2, 3, 5, 8, 13, 21 };
	for (int i = 0; i < str.size(); i++) {
		set<char> chars;
		string curstr = "";
		for (int j = i; j < str.size(); j++) {
			curstr += str[j];
			if (chars.find(str[j]) == chars.end())
				chars.insert(str[j]);
			
			for (int k = 0; k < 7; k++)
				if (fib[k] == chars.size())
					substrs.insert(curstr);
		}
	}

	return substrs;
}

int main() {
	string str;
	cin >> str;

	set<string> substrs = luckySubstr(str);
	for (auto it = substrs.begin(); it != substrs.end(); it++)
		cout << it->data() << endl;

	return 0;
}

Author：Who Watson

Link：https://wangshenghu.github.io/2016/05/10/2016-05-10-hihocoder-lucky-substrings/

Publish date：May 10th 2016, 5:37:44 pm

Update date：December 4th 2022, 5:04:45 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 解题思路
  3. 3. 时间复杂度
  4. 4. 代码
Total : 56
2022
2016
test
笔记 算法 hihoCoder 实习经历 项目