首页 > 试题广场 >

字符串问题

[编程题]字符串问题
  • 热度指数：1499 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
小摩手里有一个字符串A，小拜的手里有一个字符串B，B的长度大于等于A，所以小摩想把A串变得和B串一样长，这样小拜就愿意和小摩一起玩了。
而且A的长度增加到和B串一样长的时候，对应的每一位相等的越多，小拜就越喜欢。比如"abc"和"abd"对应相等的位数为2，为前两位。
小摩可以在A的开头或者结尾添加任意字符，使得长度和B一样。现在问小摩对A串添加完字符之后，不相等的位数最少有多少位？

输入描述:
第一行 为字符串A，第二行 为字符串B，
A的长度小于等于B的长度，B的长度小于等于100。
字符均为小写字母。


输出描述:
输出一行整数表示A串添加完字符之后，A B 不相等的位数最少有多少位？
示例1

输入

abe
cabc

输出

1
算法知识视频讲解
添加回答
wylu头像 wylu 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] a = br.readLine().toCharArray();
        char[] b = br.readLine().toCharArray();

        int n = b.length - a.length;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            int count = 0;
            for (int j = 0; j < a.length; j++) {
                if (a[j] != b[j + i]) count++;
            }
            res = Math.min(res, count);
        }
        System.out.println(res);
    }
}

发表于 2019-01-18 16:34:35 回复(0)
无心2019头像 无心2019 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string a,b;
    cin>>a;
    cin>>b;
    int n1=0,n2=0,n=0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]==b[i])
            n1++;
        if(a[i]==b[i+b.size()-a.size()])
            n2++;
    }
    cout<<a.size()-max(n1,n2)<<endl;
    return 0;
}

发表于 2019-06-19 21:15:06 回复(3)
向宇回桌头像 向宇回桌 
import java.util.*;

public class Main {
    private static final int INT_MAX = 0X3f3f3f3f;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] a = sc.next().toCharArray(), b = sc.next().toCharArray();
        int ans = INT_MAX;
        for (int i=0; i<=b.length-a.length; i++) {
            int diff = 0;
            for (int j=0; j!=a.length; j++) {
                if (a[j] != b[i+j]) { diff++; }
            }
            ans = Math.min(diff, ans);
        }
        System.out.println(ans);
    }
}
发表于 2019-02-15 11:29:40 回复(2)
J.Fan头像 J.Fan
#include<iostream>
#include<string>
usingnamespacestd;
 
intmain()
{
    string A,B;
    cin >> A;
    cin >> B;
    intlenA = A.size();
    intlenB = B.size();
    intmaxLen=0;
    for(inti=0;i<=lenB-lenA;i++)
    {
        intcurLen = 0;
        for(intj=0;j<lenA;j++)
        {
            if(A[j]==B[i+j])
                curLen++;
        }
        if(curLen > maxLen)
            maxLen = curLen;
    }
    cout << lenA-maxLen << endl;
    return0;
}
发表于 2018-07-27 17:29:21 回复(0)
牛客409434554号头像 牛客409434554号 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a,b;cin>>a>>b;
    int len=a.length(),maxn=INT_MIN;
    for(int i=0;i<=b.length()-len;i++)
    {
        string t=b.substr(i,len);
        int sum=0;
        for(int j=0;j<len;j++)
            if(t[j]==a[j])    sum++;
        maxn=max(maxn,sum);
    }
    cout<<len-maxn;
}

发表于 2022-01-24 05:09:55 回复(0)
牛客438548264号头像 牛客438548264号
在A的左右都可以添加字符，不可插入，只要找到长度和A相等，差异最小的子串，他们的差异就是我们要的解
a=input()
b=input()
res=len(a)
for i in range(len(b)-len(a)+1):
    temp=0
    for x,y in zip(a,b[i:i+len(a)]):
        if x!=y: temp+=1
    res=min(res,temp)
print(res)

编辑于 2021-06-08 14:22:49 回复(0)
牛客329247131号头像 牛客329247131号
dfs模拟
最开始是模拟往a的开头或者结尾加上b里的任意一个字符，直到新的字符串长度等于b的长度。但是由于每次都要从set{b}里取一字符，时间复杂度太高。
改变思路，a加一个字符最匹配的字符等于b减一个字符，每次比较b减去首字母和尾字母的
不相等的字符数，取最小值即可。 
A = input().strip()
B = input().strip()
dp = {}
def dfs(a, b):
    if len(a) == len(b):
        n = len(a)
        st = 0
        count = 0
        while st<n:
            if a[st] != b[st]:
                count += 1
            st += 1
        return count
    if dp.get(b):
        return dp[b]
    ans = float('inf')
    ans = min(ans, dfs(a, b[1:]), dfs(a, b[:-1]))
    dp[b] = ans
    return ans
print(dfs(A, B))


发表于 2021-04-13 18:02:42 回复(0)
啥玩意😭头像 啥玩意😭 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        char[] A = input.nextLine().toCharArray();
        char[] B = input.nextLine().toCharArray();
        int len = B.length - A.length;
        int res = Integer.MAX_VALUE;
       
        for(int i = 0;i<=len;i++){
            int count = 0;
            for(int j = 0;j<A.length;j++){
                if(A[j] !=B[j+i])
                    count++;

            }
            res = Math.min(res,count);
        }
        System.out.println(res);
    }
}

发表于 2019-04-25 16:34:42 回复(0)
大腿壮头像 大腿壮
最长公共子串问题，附带限制条件，子串不能超出主串的范围

def findLongestStr(s1, s2):
    # s1:主串
    # s2：匹配串
    dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
    max_value = 0
    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 1):
            if s1[i - 1] == s2[j - 1] and i >= j and i - j <= len(s1) - len(s2):
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = 0
            max_value = max(max_value, dp[i][j])
    return len(s2) - max_value
发表于 2019-03-15 20:13:57 回复(0)
乐观的摸摸头17头像 乐观的摸摸头17 
import sys

aStr = sys.stdin.readline().strip()
bStr = sys.stdin.readline().strip()
max = 0
for i in range(len(bStr)-len(aStr)+1):
    count = 0
    for j in range(len(aStr)):
        if(aStr[j] == bStr[i+j]):
            count += 1
    if(max < count):
        max = count
print (len(aStr)-max)

发表于 2018-09-05 01:18:34 回复(0)
G201806011649877头像 G201806011649877

答案都这么写吗。。好吧是我想复杂了。。我以为题目中abc和abd这个例子还必须要顺序相同。。有没有跟我这么想得。。😂


发表于 2018-09-01 02:53:34 回复(1)
Tracy293头像 Tracy293
import java.util.Scanner;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
        String m=sc.next();
        String b=sc.next();
        char[] mo=m.toCharArray();
        char[] bye=b.toCharArray();
        if(mo.length>bye.length)
            continue;
         int n=0;
         int d=0;
         for(int i=0;i<mo.length;i++){
             for(int j= i;j<bye.length;j++){
                 if(mo[i]==bye[j]){
                     n++;
                     break;
                 }
             }
         }
         d=mo.length-n;
         System.out.println(d);
        }
    }
}

发表于 2018-08-31 23:57:47 回复(0)
Alex6666头像 Alex6666
寻找A与B的字串最多相同字母
#include<iostream>
#include<string>
using namespace std;
int main()
{
    string A,B;
    cin>>A>>B;
    int la=A.length();
    int lb=B.length();
    intmax=0;
    for(int i=0;i<lb-la+1;++i)
    {
        int count=0;
        for(int j=0;j<la;++j)
        {
            if(A[j]==B[i+j])
                ++count;
        }
        if(max<count)
            max=count;
    }
    cout<<la-max<<endl;
    return 0;
}
发表于 2018-07-31 11:24:48 回复(0)
WAK头像 WAK
#include<bits/stdc++.h>
usingnamespacestd;
intmain(){
    string a,b;
    while(cin>>a>>b){
        intdif = INT_MAX;
        for(inti = 0;i<=b.size()-a.size();i++){
            intnum = 0;
            for(intj = 0;j<a.size();j++){
                if(a[j]!=b[j+i])
                    num++;
            }
            dif = dif<num?dif:num;
        }
        cout<<dif<<endl;
    }
    return0;
}
发表于 2018-07-18 17:28:33 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 字符串 模拟 前端工程师 穷举 算法工程师 摩拜 PHP工程师 Java工程师
来自：摩拜2018校招算法工...
上传者：小小
难度：
14条回答 4116浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号