代码之家 › 专栏 › 技术社区 › Outcast

只有数字的最长子串的长度

text-processing python

Outcast · 技术社区 · 5 年前

我想输入一个字符串,输出一个只有数字的最长子字符串的长度。

不过,首先,我希望在“只包含数字的子字符串”定义上更灵活一些。

具体地说,我想对子串做我想做的事情,这些子串至少包含70%的数字(所以不一定是100%)。

因此,如果我有这句话:

sentence = 'I am 14 a data 1,a211 899 scientist 1he3'

那么答案应该是 10 来自子串 1,a211 899 因为这个子串有7/10个字符(70%)作为数字。

不必(所以)考虑空白,这样,如果这样做对您更方便的话,您可以从一开始就删除它们。

我怎样才能有效地做到这一点?

2 回复 | 直到 5 年前

RomanPerekhrest 5 年前

用 re_pattern.finditer 函数和特定正则表达式模式:

import re

sentence_1 = 'I am 99 a data 1,211 scientist'
pat = re.compile(r'\b\d+(?:[.,]\d+)?')   # prepared pattern
max_num_len = max(len(m.group()) for m in pat.finditer(sentence_1))
print(max_num_len)  # 5

附加的 扩展的 更新条件的方法 “由至少70%的数字组成的最长子串(所以不一定是100%)。” :

sentence = 'I am 14 a data 1,a211 899 scientist 1he3'
num_percent = 70

main_pat = re.compile(r'\b\S*\d+\S*(?:\s*\S*\d+\S*){1,}')
nondigits_pat = re.compile(r'\D+')  # pattern to match non-digit characters
max_substr_len = 0

for m in main_pat.finditer(sentence):
    val = m.group()  # matched substring value
    val_len = len(val)
    if (len(nondigits_pat.sub('', val)) / val_len * 100 >= num_percent) \
            and val_len > max_substr_len:
        max_substr_len = val_len

print(max_substr_len)   # 10

adnanmuttaleb 5 年前

1) 此解决方案不适用于空白区域,但比其他解决方案更有效(请检查以下内容):

s = 'I am 14 a data 1,a211 scientist 1he3'

def check(w):
    digits = [d for d in w if d.isdigit()]
    return len(digits)/len(w) >= 0.6


l = s.split()

result = ''
for w in l:
    if check(w):
       if len(w) > len(result):
           result = w

print(result)

输出:

1,a211

2) 如果还要考虑空格,则应检查每个子字符串的条件,该条件包含不少于60%的数字:

s1 = 'I am 14 a data 1,a211 scientist 1he3'
s2 = 'I am 14 a data 1,a211 889 scientist 1he3' 

#this function is predicate that check if substring hold more then 60% of digits
def check(w):
    digits = [d for d in w if d.isdigit()]
    return len(digits)/len(w) >= 0.6

def get_max(s):
  result = ''
  for i in range(len(s)):
    for j in range(i+1, len(s)):
      #check if the substring is valid and have larger size 
      if check(s[i:j]):
        if (j-i) > len(result):
          result = s[i:j]
  return result

print(get_max(s1))
print(get_max(s2))

输出:

1,a211
1,a211 889

最后一个解决方案的时间复杂性为 O(n^2) ,而第一个是 O(n) 在哪里 n 是字符串的大小。

Paul M. 5 年前

灵感来自@adnanmuttaleb的代码。不要检查所有的片/子串,只检查那些以数字开头和结尾的片/子串。我相信时间复杂度(或者至少迭代次数)是:o(n!/(2*(n-2)!)其中“n”是原始字符串中的位数。此计算不考虑itertools.combinations的复杂性。

def get_longest_substring(string):

    from itertools import combinations

    def is_valid_substring(substring):
        return len([char for char in substring if char.isdigit()]) / len(substring) >= 0.7

    digit_indecies = [index for index, char in enumerate(string) if char.isdigit()]

    substrings = []
    for begin, end in combinations(digit_indecies, 2):
        substring = string[begin: end+1]
        if is_valid_substring(substring):
            substrings.append(substring)
    return max(substrings, key=len)

def main():

    string = "I am 14 a data 1,a211 899 scientist 1he3"

    longest_substring = get_longest_substring(string)
    print(longest_substring)

    return 0


if __name__ == "__main__":
    import sys
    sys.exit(main())

输出:

1,a211 899