具有 K 个不同字符的字符串的子序列数
Number of subsequences of a string with K distinct characters
我想解决一个问题,我需要一些帮助,因为我的代码不起作用。
好的,所以我有一个序列 S(输入数据),我需要找到子序列的数量,使得不同字符的子序列数必须等于 K(输入数据)
示例:
For S = abcaa and K = 3, the answer is 5.
s1 = abc
s2 = abca
s3 = abcaa
s4 = bca
s5 = bcaa
我想了想,在互联网上寻找一些答案,但没有找到我真正想要的。
所以,我认为我必须按顺序找到每个字符的频率,但我不知道之后该怎么做...
这不是最有效的解决方案,但您可以这样做:
首先遍历您的字符串,对于每个位置,您需要做两件事。首先,从该位置开始迭代,直到找到 k 个不同的字符(为此使用频率数组)或直到到达字符串的末尾。如果找到子序列,从停止的位置 + 1 开始再次迭代,当找到的字符已经在频率向量中并且尚未到达字符串末尾时,计算找到的字母数.您将 1 添加到该数字(因为第一个子序列)然后您就可以找到该位置的所有子序列。然后你增加你的第一个索引并继续。
Ruby 解决方案:
S="abcaa"
k=3
distinct_arr = []
result = 0
S_arr = S.split("")
while S_arr.length != 0
S_arr.each do |char|
if !distinct_arr.include? (char)
distinct_arr << char
end
if distinct_arr.length == k
result = result + 1
end
if distinct_arr.length == k + 1
break
end
end
S_arr.shift
distinct_arr = []
end
puts result
我想解决一个问题,我需要一些帮助,因为我的代码不起作用。
好的,所以我有一个序列 S(输入数据),我需要找到子序列的数量,使得不同字符的子序列数必须等于 K(输入数据)
示例:
For S = abcaa and K = 3, the answer is 5.
s1 = abc
s2 = abca
s3 = abcaa
s4 = bca
s5 = bcaa
我想了想,在互联网上寻找一些答案,但没有找到我真正想要的。 所以,我认为我必须按顺序找到每个字符的频率,但我不知道之后该怎么做...
这不是最有效的解决方案,但您可以这样做: 首先遍历您的字符串,对于每个位置,您需要做两件事。首先,从该位置开始迭代,直到找到 k 个不同的字符(为此使用频率数组)或直到到达字符串的末尾。如果找到子序列,从停止的位置 + 1 开始再次迭代,当找到的字符已经在频率向量中并且尚未到达字符串末尾时,计算找到的字母数.您将 1 添加到该数字(因为第一个子序列)然后您就可以找到该位置的所有子序列。然后你增加你的第一个索引并继续。
Ruby 解决方案:
S="abcaa"
k=3
distinct_arr = []
result = 0
S_arr = S.split("")
while S_arr.length != 0
S_arr.each do |char|
if !distinct_arr.include? (char)
distinct_arr << char
end
if distinct_arr.length == k
result = result + 1
end
if distinct_arr.length == k + 1
break
end
end
S_arr.shift
distinct_arr = []
end
puts result