计算文本间距的实现

痛定思痛。 2022-04-02 03:57 154阅读 0赞

我们可以使用动态规划的方式来计算文本间距，通过建立DP数组将对比文本的问题分成多个子问题:  
文本间的间距通常包含以下三种情况：  
insert： abc -> abdc  
remove: abc -> ab  
update: abc -> adc  
我们只需要计算不同情况下最短间距就可以了，具体实现方式如下：

def text_distance(str1, str2):
        m, n = len(str1), len(str2)
    
        # 构建二维数组来存储子问题的答案
        dp = [[0 for x in range(n+1)] for x in range(m+1)]
    
        # 利用动态规划算法，填充数组
        for i in range(m+1):
            for j in range(n+1):
    
                # 假设第一个字符串为空，则转换的代价为j(j次的插入)
                if i == 0:
                    dp[i][j] = j
    
                # 同样，假设第二个字符串为空，则转换的代价为i(i次的插入)
                elif j == 0:
                    dp[i][j] = i
    
                # 如果最后一个字符相等，就不会产生代价
                elif str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
    
                # 如果最后一个字符不一样，则考虑多种可能性，并且选择其中的最小值
                else:
                    dp[i][j] = 1 + min(dp[i][j-1],      # Insert
                                      dp[i-1][j],       # Remove
                                      dp[i-1][j-1])     # Replace
        return dp[m][n]

我们可以验证一下

text_distance('go', 'going')     # output:3
    text_distance('whose', 'who')     # output:2
    text_distance('who', 'how')     # output:2

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

还没有评论，来说两句吧...

相关阅读

相关华为OD机试 Java【计算间距】

描述小明得到了一项任务，在一个沙地里种树。不过，有些地方不能种树，只能选特定的位置来种。为了让树之间的空间尽可能大，从而更好地防沙，你要帮小明决定每棵树应该种在哪里。

Bertha 。/ 2024年02月05日 23:14/ 0 赞/ 8 阅读

相关华为OD机试 C++【计算间距】

描述小明得到了一项任务，在一个沙地里种树。不过，有些地方不能种树，只能选特定的位置来种。为了让树之间的空间尽可能大，从而更好地防沙，你要帮小明决定每棵树应该种在哪里。

迷南。/ 2024年02月05日 23:14/ 0 赞/ 32 阅读

相关 iOS设置富文本行间距、字间距

[Demo下载地址][Demo] 我们在展示文字信息时，经常会碰到换行自适应高度的文本，这时我们会发现换行之后，文本之间的行间距依然很小，导致看起来很拥挤，影响美观。因

蔚落/ 2023年10月17日 15:10/ 0 赞/ 109 阅读

相关 CSS文本属性-文本颜色、文本对齐、文本装饰、文本缩进、行间距

CSS文本属性 CSS Text（文本）属性可以定义文本的外观，比如颜色，对齐方式，装饰文本，文本缩进等。文本颜色 color属性用于定义文本的颜色。 <ta

Love The Way You Lie/ 2022年12月16日 14:28/ 0 赞/ 111 阅读

相关 ios开发之改变文本行间距和字符间距

[ios开发之改变文本行间距和字符间距][ios_] \import <UIKit/UIKit.h> @interface LineSpaceLabel :

冷不防/ 2022年09月24日 14:19/ 0 赞/ 609 阅读

相关笔记指定n天间距日期的计算

原理很简单，一天的时间的毫秒数是1000606024，前n天的日期就是现在日期换成毫秒-n1000606024。再把这个值换成日期即可（通过setTime方法）

水深无声/ 2022年06月05日 03:14/ 0 赞/ 322 阅读

相关 iOS UILabel设置行间距和字间距并计算高度

NSString \labelText = goods.goods\_2; NSMutableAttributedString \attributedStr

刺骨的言语ヽ痛彻心扉/ 2022年06月02日 01:28/ 0 赞/ 287 阅读

相关计算文本间距的实现

我们可以使用动态规划的方式来计算文本间距，通过建立DP数组将对比文本的问题分成多个子问题: 文本间的间距通常包含以下三种情况： insert： abc -> abdc

痛定思痛。/ 2022年04月02日 03:57/ 0 赞/ 155 阅读

相关 Java文本处理9-计算文本句子数

1、任务简介本节任务是计算文本中的句子数，并且对于句子数的划分标准为“。” “！”和“？”三种符号。 -------------------- 2、基本任务和代码

逃离我推掉我的手/ 2022年03月18日 06:56/ 0 赞/ 209 阅读

相关 CSS设置文本——行间距

<1>.用比例设置行间距 1 <html> 2 <head> 3 <style type="text/css"> 4

柔光的暖阳◎/ 2021年11月11日 11:52/ 0 赞/ 400 阅读