经过一番努力,我终于让这个程序运行起来了,至少在我测试过的少数几个测试用例中是这样。这是我从CodeWars那里得到的一个挑战,任务是制作一个程序,它接受一个输入字符串(按顺序,或被置乱)并返回一个布尔值,无论该输入是否由重复的子字符串组成。在
我的方法是使用itertools.排列列出从给定的字符串输入中可以生成的所有可能的字符串,然后使用正则表达式来匹配其中的每一个。保证可以工作,但复杂性指数级,这导致我的笨拙的Intel i5 w/8Gig内存错误,输入只有len()==12的3个唯一字符。在
必须有一种更有效的方法来运行它(最好是在Python中,在Pypy/C扩展中这样做超出了这个分配的范围)
够了,我的代码是:
def has_subpattern(string):
'''input: a string. Output: boolean: whether the input str is made of a
smaller repeating substring. '''
import re
from itertools import permutations
if len(string) <= 1:
return False
# check if the input has a repeating subpattern (in case it's not scrambled)
if bool( re.match(r'(.+?)\1+$', string)) == True:
return True
# create a set of the permutation of a string ( to remove duplicates)
perms = set([''.join(p) for p in permutations(string)])
pattern = re.compile(r'(.+?)\1+$')
print('# of permutations: ', len(perms))
print(perms)
# iterate through the list of permutations, checking if any has #subpattern
for perm in perms:
if bool((re.match(pattern, perm))) == True:
print((re.match(pattern, perm)), perm)
return True
return False
string=“123a213a321a” 打印(有_子模式(字符串))
有什么建议可以用来减少运行时间?我是个新手,完全不知所措。在
在对计数器进行了一番讨论之后,我根据论坛上的建议创建了一个解决方案,它使用计数器,并且比针对regex强制所有排列都便宜几个数量级:
我得到的是:
我认为你走错路了。如果可以对其进行加扰,则只需检查每个字符的计数是否相同。在javascript中,可以执行以下操作:
function isRepeating(str) { var characters = str.split(''); if (characters.length < 2) { return false; } var characterCounts = characters.reduce(function(carry, char) { carry[char] = carry[char] ? carry[char] + 1 : 1; return carry; }, {}); var counts = Object.values(characterCounts); return !counts.some(c => c !== counts[0]); } console.log(isRepeating("123a123a321a")); // true console.log(isRepeating("hello")); // false console.log(isRepeating("racecar")); // false console.log(isRepeating("raceecar")); // true
;对于python,只需遵循相同的方法-计数每个字符出现的次数,看看每个字符是否具有相同的计数。在
dave帖子中的counter方法的python是:
方法是对所有字符进行计数,然后通过在计数器中获取一组值来检查计数是否相同。如果集合中只有一个数字,则所有字符都有相同的计数,并且是加扰子串。在