首页 > 试题广场 >

LUCKY STRING

[编程题]LUCKY STRING

热度指数：12001 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

A string s is LUCKY if and only if the number of different characters in s is a fibonacci number. Given a string consisting of only lower case letters , output all its lucky non-empty substrings in lexicographical order. Same substrings should be printed once.

输入描述:

a string consisting no more than 100 lower case letters.

输出描述:

output the lucky substrings in lexicographical order.one per line. Same substrings should be printed once.

示例1

输入

aabcd

输出

a 
aa 
aab 
aabc 
ab 
abc 
b 
bc 
bcd 
c 
cd 
d

算法知识视频讲解

Python

离疏

def islucky(ss):#判断是否是幸运数字
    if len(set(ss)) in Fibonacci:
        return True
    else:
        return False

def string(ss):#求所有子字符串
    results = []
    for x in range(len(s)):# x + 1 表示子字符串长度
        for i in range(len(s) - x):# i 表示偏移量
            results.append(s[i:i + x + 1])
    return results

s=input()
Fibonacci=[1,2,3,5,8,13,21]#26以内的feibonacci数（26个字母）
ans=list(set(string(s)))#set去重
ans.sort()#按字典序排序
for i in ans:
    if islucky(i):
        print(i)

发表于 2018-08-17 15:45:01 回复(0)

Python

L.W.M

strings = raw_input()
fib = set([1, 2, 3, 5, 8, 13, 21, 34, 55, 89])
ans = set([])
for i in range(len(strings)):
    nowset = set([])
    count = 0
    for j in range(i, len(strings)):
        if not strings[j] in nowset:
            count += 1
            nowset.add(strings[j])
        if count in fib:
            ans.add(strings[i:j + 1])
ans = list(ans)
ans = sorted(ans,key=str.lower)
for item in ans:
    print item

发表于 2017-09-24 14:28:27 回复(0)

Python

康星星


#!/user/bin/python
# coding=utf-8
def isFibonacci(n):
	f = [0,1,1]
	for i in range(3,15):
		fib = f[i-1] + f[i-2]
		if fib > 100:
			break
		f.append(fib)
	if n in f:
		return True
	else:
		return False

def luckynum(s):
	set_str = set(s)
	num = 0
	for i in set_str:
		num += 1
	return num
	
def subStrings(s):
	a = []
	h = {}
	length = len(s)
	for i in range(1,length + 1):
		for j in range(length - i + 1):
			temp = s[j:j+i]
			if isFibonacci(luckynum(temp)):
				h[temp] = 1
	a = h.keys()
	a.sort()
	return a

str = raw_input()
result = subStrings(str)
for r in result:
	print r

编辑于 2016-10-01 00:07:52 回复(0)