首页 > 试题广场 >

特殊的编辑距离

[编程题]特殊的编辑距离

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

在自然语言处理的过程中，经常需要判断一个字符串和另外一个字符串之间的一个相似程度，其中常见的一个指标就是编辑距离，即一个字符串最少经过多少次“增删改”某个字符，可以变为另一个字符串。

如“abc”与“ac”的编辑距离为1，是因为在a和c中间“增加”一个b即可。如“abcd”与“axc”的编辑距离为2，是因为把“abcd”的b修改为x，然后再删除d即可，共2次操作。

但是在某种场景中，编辑距离定义为词粒度的。比如句子A “I am a coder”与句子B “hello , I am a singer”之间，对于句子A可以通过添加"hello"和符号",", 并替换"coder"为"singer"，共3个操作得到句子B。所以可得其基本的编辑距离为3。

在本题中，特别地，对于部分词，比如标点符号“, ”、"hello"对于句子语义的影响并不重要，这部分称之为停用词，这部分可以在匹配的过程中被跳过。比如对于句子A “I am a coder”与句子B “hello , I am a singer”，如果加入了停用词的影响，那编辑距离从3降到1。

所以目标是可以有选择性地跳过停用词的情况下，问最小的编辑距离是多少。

输入描述:

共3行
第一行为停用词列表，用空格区分
第二行为句子A，所有词可以用空格区分，词数不超过10000
第三行为句子B，所有词可以用空格区分，词数不超过10000

输出描述:

一个整数，可跳过停用词情况下的最短编辑距离

示例1

输入

hello ,
I am a coder
hello ,  I am a singer

输出

说明

见题意

示例2

输入

hello , ?
I am a boy
are you a girl ?

输出

说明

I am boy 需要进行编辑

算法知识视频讲解

pein531

1.先将句子中的停用词去除掉；

2.然后按空格将句子划分为词的粒度；

3.最后用常规的动态规划方法计算编辑距离即可。

stop_words = input().split()
sentence1 = input()
sentence2 = input()
# 先将句子中的停用词去除
for word in stop_words:
    sentence1 = sentence1.replace(word, "")
    sentence2 = sentence2.replace(word, "")
s1 = sentence1.split()
s2 = sentence2.split()
# 计算句子中的单词数
word_num1 = len(s1)
word_num2 = len(s2)
# 动态规划计算编辑距离
dp = [[0] * (word_num2 + 1) for _ in range(word_num1 + 1)]
for i in range(word_num1 + 1):
    for j in range(word_num2 + 1):
        if i == 0 and j == 0:
            dp[i][j] = 0
        elif i == 0 and j > 0:
            dp[0][j] = j
        elif i > 0 and j == 0:
            dp[i][0] = i
        elif s1[i - 1] == s2[j - 1]:
            dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1] + 1, dp[i - 1][j] + 1)
        else:
            dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i][j - 1] + 1, dp[i - 1][j] + 1)
print(dp[word_num1][word_num2])

编辑于 2021-01-18 14:34:56 回复(0)

Handa_Rei

import sys
from functools import cache,lru_cache
from typing import List
 
sys.setrecursionlimit(10000)
def preProcess(a: str, stop: List[str]):
    for word in stop:
        a = a.replace(word, '')
    return a.strip().split()
 
 
stop = input().split()
a = input()
b = input()
a = preProcess(a, stop)
b = preProcess(b, stop)
m, n = len(a), len(b)
 
@lru_cache(None)
def dfs(i: int, j: int):
    if i == 0:
        return j
    if j == 0:
        return i
    if a[i - 1] == b[j - 1]:
        return dfs(i - 1, j - 1)
    else:
        return min(dfs(i - 1, j - 1),dfs(i - 1, j),dfs(i, j - 1)) + 1
print(dfs(m,n))

发表于 2023-08-26 17:29:47 回复(0)

牛客634241998号

import java.util.ArrayList;
import java.util.Scanner;

/**思路：和字符串的编辑距离非常类似，首先把输入的两个字符串中的无效字符剔除，然后类似于编辑距离的算法采用动态规划求解
* @author wangshuli
* @create 2022-09-18 15:30
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String stop = scanner.nextLine();
String[] s1 = scanner.nextLine().split(" ");
String[] s2 = scanner.nextLine().split(" ");
solve(stop,s1,s2);
}

private static void solve(String stop, String[] s1, String[] s2) {
String[] stopped = stop.split(" ");

ArrayList<String> list1 = new ArrayList<>();
for(String s:s1){
boolean contains=false;
for(String tmp:stopped){
if(s.equals(tmp)){
contains=true;
break;
}
}
if(contains==false){
list1.add(s);
}
}
ArrayList<String> list2 = new ArrayList<>();
for(String s:s2){
boolean contains=false;
for(String tmp:stopped){
if(s.equals(tmp)){
contains=true;
break;
}
}
if(contains==false){
list2.add(s);
}
}
minLen(list1, list2);
}

private static void minLen(ArrayList<String> list1, ArrayList<String> list2) {
int n = list1.size();
int m = list2.size();
int[][] dp = new int[n + 1][m + 1];//dp[i][j]代表list1前i个变成list2的前j个最小距离
for(int i=0;i<=n;i++){
dp[i][0] = i;
}
for(int j=0;j<=m;j++){
dp[0][j]=j;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(list1.get(i-1).equals(list2.get(j-1))){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j] = Math.min(Math.min(dp[i-1][j]+1,dp[i-1][j-1]+1),dp[i][j-1]+1);
}
}
}
System.out.println(dp[n][m]);
}

}

发表于 2022-09-18 16:45:59 回复(0)

菲尼克斯弗兰克

来一个java版本的答案

import java.util.*;
public class Main {
    // 特殊的编辑距离-动态规划
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Set<String> words = new HashSet<>();
        String[] s = in.nextLine().split(" ");
        Collections.addAll(words, s);
        String[] a = in.nextLine().split(" ");
        String[] b = in.nextLine().split(" ");
        ArrayList<String> la = new ArrayList<>();
        ArrayList<String> lb = new ArrayList<>();
        for (String value : a) {
            if (!words.contains(value)) la.add(value);
        }
        for (String value : b) {
            if (!words.contains(value)) lb.add(value);
        }
        fun(la, lb);
    }
    // 编辑距离模板
    public static void fun(ArrayList<String> a, ArrayList<String> b) {
        int m = a.size(), n = b.size();
        int[][] dp = new int[m+1][n+1];
        // base case
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (a.get(i-1).equals(b.get(j-1))) { // 相同时
                    dp[i][j] = dp[i-1][j-1];
                } else { // 不同时
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;
                }
            }
        }
        System.out.println(dp[m][n]);
    }
}

发表于 2022-09-04 18:49:41 回复(0)

ryanlee98

裸题，参考leetcode 编辑距离

把两个字符串中的停用词去掉，剩下的就没什么新鲜事了

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
int main() {
    unordered_set<string> st;
    vector<string> s1;
    vector<string> s2;
    string temp;
    do {
        cin>>temp;
        st.insert(temp);
    }while(cin.get() != '\n');
    do {
        cin>>temp;
        if (st.count(temp)) continue;
        s1.push_back(temp);
    }while(cin.get() != '\n');
    do {
        cin>>temp;
        if (st.count(temp)) continue;
        s2.push_back(temp);
    }while(cin.get() != '\n');

    int len1 = s1.size(), len2 = s2.size();
    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));
    for (int i = 0; i <= len1; i++)
        for (int j = 0; j <= len2; j++) {
            if (i == 0 || j == 0) dp[i][j] = max(i, j);
            else if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
        }
    cout<< dp[len1][len2];
}

发表于 2022-03-26 00:07:32 回复(0)

C/C++

球球来个offer吧~

//dp求编辑裸题

#include<bits/stdc++.h>

using namespace std;
int dp[1001][1001];
vector<string>d,a,b,anew,bnew;
unordered_map<string,int>mp;
int levenshtein(vector<string> a ,vector<string> b)//编辑距离O(n^2)
{
dp[0][0]=0;
for(int i=1;i<=a.size();i++) dp[i][0]=i;
for(int j=1;j<=b.size();j++) dp[0][j]=j;
for(int i=1;i<=a.size();i++)
for(int j=1;j<=b.size();j++){
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
if(a[i-1]!=b[j-1]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
else dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
}
return dp[a.size()][b.size()];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
string disableword,s1,s2;
getline(cin,disableword);
stringstream ss;
ss<<disableword;
while(ss>>disableword){
d.emplace_back(disableword);
}
getline(cin,s1);
ss.clear();
ss.str("");
ss<<s1;
while(ss>>s1){
a.emplace_back(s1);
}
getline(cin,s2);
ss.clear();
ss.str("");
ss<<s2;
while(ss>>s2){
b.emplace_back(s2);
}
for(int i=0;i<d.size();i++)
mp[d[i]]=1;
for(int i=0;i<a.size();i++)
if(!mp[a[i]])
anew.emplace_back(a[i]);
for(int i=0;i<b.size();i++)
if(!mp[b[i]])
bnew.emplace_back(b[i]);
cout<<levenshtein(anew,bnew)<<endl;
return 0;
}

发表于 2021-01-10 11:21:25 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师算法工程师网易测试开发工程师测试工程师安全工程师 2021 大数据开发工程师 Java工程师

上传者：小小

难度：

6条回答 31收藏 2807浏览

通过挑战的用户

739454217

2022-11-05 17:17:36
牛客63424...

2022-09-18 16:18:11
菲尼克斯弗兰克

2022-09-04 18:48:17
清梦.

2022-09-03 22:06:43
🌸20180...

2022-09-03 19:58:04

特殊的编辑距离

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题