字符串距离

[编程题]字符串距离

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

给定一个字符串str，和一个字母ch，请实现相应的代码求出一个数组，使数组中每个数字表示该位置与字母ch之间的最短距离。
比如str=”lexinfintech” ch=”i”
则输出为：[3,2,1,0,1,1,0,1,2,3,4,5]

输入描述:

第一行为字符串

第二行为字母

输出描述:

一个数字数组

示例1

输入

lexinfintech
i

输出

[3,2,1,0,1,1,0,1,2,3,4,5]

备注:

假定所有输入的字符ch都在字符串str中，且str中的所有字母为小写，str长度不超过10000

算法知识视频讲解

Python

Fishar


	s = input()
ch = input()
l = len(s)
re = []
for i in range(l):
    if s[i] == ch:
        re.append(i)
relist = []
if re is None:
    print([l for i in range(l)])
else:
    for i in range(l):
        minVal = l
        for j in re:
            if abs(i - j) < minVal:
                minVal = abs(i - j)
        relist.append(minVal)
    print(str(relist).replace(' ',''),end='')

编辑于 2019-06-28 23:29:45 回复(0)

Python

_Aston_

解法 1：比较暴力

def func1(test_str, target):
    result_list = [0 if c == target else 9999 for c in test_str]
    last_target, str_len = 0, len(test_str)
    for i, distance in enumerate(result_list):
        if distance == 0:
            for k in range(last_target, i):                 # 向前填数
                temp_distance = i-k
                if result_list[k] > temp_distance:
                    result_list[k] = temp_distance
            for k in range(i+1, str_len):                   # 向后填数
                if result_list[k] == 0:
                    break
                temp_distance = k-i
                if result_list[k] > temp_distance:
                    result_list[k] = temp_distance
            last_target = i
    print_str = '[' + ','.join([str(i) for i in result_list]) + ']'
    print(print_str)
if __name__ == '__main__':
    input_str, input_target = input(), input()
    func1(input_str, input_target)

解法 1：
合并了两个循环，但是效率更低了

def func1(test_str, target):
    result_list = [0 if c == target else 9999 for c in test_str]
    last_target, str_len = -1, len(test_str)
    for i, distance in enumerate(result_list):
        if distance == 0:
            range_l = list(range(last_target+1, i)) + list(range(i+1, str_len))
            for k in range_l:
                if result_list[k] == 0:
                    break
                temp_distance = abs(k-i)
                if result_list[k] > temp_distance:
                    result_list[k] = temp_distance
            last_target = i
    print_str = '[' + ','.join([str(i) for i in result_list]) + ']'
    print(print_str)
if __name__ == '__main__':
    input_str, input_target = input(), input()
    func1(input_str, input_target)

解法 2：二分法

import math
def func1(test_str, target):
    target_index_list = [i for i, c in enumerate(test_str) if c == target]
    result_list = []
    str_len, i_list_len = len(test_str), len(target_index_list)
    for i, index in enumerate(target_index_list):
        start = 0 if i == 0 else \
            math.ceil((target_index_list[i-1] + target_index_list[i] + 1) / 2)
        end = str_len-1 if i == i_list_len-1 else \
            math.ceil((target_index_list[i] + target_index_list[i+1] - 1) / 2)
        for k in range(start, end+1):
            if k != target_index_list[i]:
                result_list.append(abs(target_index_list[i]-k))
            else:
                result_list.append(0)
    print_str = '[' + ','.join([str(i) for i in result_list]) + ']'
    print(print_str)
if __name__ == '__main__':
    input_str, input_target = input(), input()
    func1(input_str, input_target)

编辑于 2018-12-18 18:16:46 回复(0)