首页 > 试题广场 >

判断两个字符串是否为变形词

[编程题]判断两个字符串是否为变形词

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

给定两个字符串str1和str2，如果str1和str2中出现的字符种类出现的一样且每种字符出现的次数也一样，那么str1和str2互为变形词。请判断str1和str2是否为变形词。

输入描述:

输入包括3行，第一行包含两个整数n，m分别代表str1和str2的长度，第二行和第三行为两个字符串，分别代表str1和str2。

输出描述:

如果str1和str2互为变形词，请输出“true”，否则输出“false”。

示例1

输入

3 3
123
321

输出

true

示例2

输入

3 4
123
2331

输出

false

备注:

时间复杂度，空间复杂度。

算法知识视频讲解

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    string s1,s2;
    cin>>s1>>s2;
    map<char,int>m1,m2;
    for(int i=0;i<s1.size();i++)
        m1[s1[i]]++;
    for(int i=0;i<s2.size();i++)
        m2[s2[i]]++;
    if(m1==m2)
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;
    return 0;
}

发表于 2019-09-12 22:18:40 回复(1)

GeniusIOTboy

#include <iostream>
#include <string>

using namespace std;

const int maxn=127+1;
int a[maxn]={0},b[maxn]={0};

int main()
{
    int n,m;
    cin>>n>>m;

    if(n!=m)
    {
    	cout<<"false"<<endl;
    	return 0;
    }

    string str1,str2;
    cin>>str1>>str2;

    for(int i=0;i<n;++i)
    {
       a[str1[i]]++;
       b[str2[i]]++;
    }

    for(int j=0;j<128;++j)
    {
    	if(a[j]!=b[j])
    	{
    		cout<<"false"<<endl;
    		return 0;
    	}
    }

    cout<<"true"<<endl;

    return 0;
}

发表于 2019-10-15 10:53:33 回复(0)

pein531

依题意中对变形词的定义进行判断即可

n, m = map(int, input().strip().split())
s1 = input().strip()
s2 = input().strip()
counter1 = dict()
counter2 = dict()
for w in s1:
    if w in counter1:
        counter1[w] += 1
    else:
        counter1[w] = 1
for w in s2:
    if w in counter2:
        counter2[w] += 1
    else:
        counter2[w] = 1
if len(counter1) != len(counter2):
    print("false")
else:
    for w in counter1:
        if counter1[w] != counter2[w]:
            print("false")
            break
    else:
        print("true")

发表于 2021-06-01 22:19:22 回复(0)

復活の検事

这题的测试样例有问题

它没有保证len1等于str1的长度或者len2等于str2的长度，所以程序中不能使用len1和len2，而要用str.length()。希望牛客网能认真出题

发表于 2020-05-05 09:06:22 回复(5)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    string a, b;
    cin>>n>>m>>a>>b;
    if(n != m){
        puts("false");
        return 0;
    }
    map<char, int> mp1, mp2;
    for(int i=0;i<n;i++){
        mp1[a[i]]++;
        mp2[b[i]]++;
    }
    for(auto &u:mp1){
        char k = u.first;
        int v = u.second;
        if(mp2.find(k)==mp2.end() || mp2[k]!=v){
            puts("false");
            return 0;
        }
    }
    puts("true");
    return 0;
}

发表于 2020-04-15 00:59:35 回复(0)

Java

小比例福

解题思路参考左神的解法，详见程序员代码面试指南。

ps:若有不妥之处，望请相互交流，多谢。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String str1 = sc.next();
        String str2 = sc.next();
        if (isDeformation(str1, str2) == true) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }
    public static boolean isDeformation(String str1, String str2) {
        //优先考虑判空操作
        if (str1 == null || str2 == null || str1.length() != str2.length()) {
            return false;
        }
        //定义一个整形数组map，用于存储每一个字符出现的次数。
        int[] map = new int[256];//如果字符个数足够多，可以申请一个散列表。
        for (int i = 0; i < str1.length(); i++) {
            //map数组存储每一个字符出现的次数
            map[str1.charAt(i)]++;
        }
        for (int i = 0; i < str2.length(); i++) {
            //如果map数组的值小于0，则返回false
            if (map[str2.charAt(i)]-- < 0) {
                return false;
            }
        }
        return true;
    }
}

发表于 2019-09-27 15:01:16 回复(3)

和风春袭远

import java.util.Scanner;

public class Main {
    public static boolean isDeformation(String str1, String str2) {
        if (str1.length() != str2.length()) {
            return false;
        }
        char[] chas1 = str1.toCharArray();
        char[] chas2 = str2.toCharArray();
        int[] map = new int[256];
        for (int i=0; i<chas1.length; i++) {
            map[chas1[i]]++;
        }
        for (int i=0; i<chas2.length; i++) {
            if (map[chas2[i]]-- == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str1 = sc.next();
        String str2 = sc.next();
        sc.close();
        System.out.println(isDeformation(str1, str2));
    }
}

发表于 2021-09-18 20:44:38 回复(0)

Python 3

毓毓子最可爱

m,n=input().split()
str1=input()
str2=input()
result="true"
#将字符串转换为集合进行统计
for i in set(str1):
    if str1.count(i)!=str2.count(i):
        result="false"
        break
print(result)

发表于 2021-08-09 09:00:05 回复(0)

牛客887263087号

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main(void){
int n, m;
cin >> n;
cin >> m;
string s1;
string s2;
cin >> s1;
cin >> s2;
unordered_map<char, int> m1;
unordered_map<char, int> m2;
for(int i = 0; i < n; i++){
char c = s1[i];
if(m1[c] == 0)
m1[c] ++;
else
m1[c] ++;
}
for(int i = 0; i < m; i++){
char c = s2[i];
if(m1[c] == 0){
cout << "false" << endl;
return 0;
}else{
m1[c]--;
}
}
for(auto e : m1){
if(e.second != 0){
cout << "false" << endl;
return 0;
}
}
cout << "true" << endl;
return 0;

}

使用一个unordered_map来遍历

使用unordered_map的方法总结

在添加元素时技巧如下：

if :: umap[c] == 0

umap[c] ++;

else ::

umap[c] ++;

判断元素不存在 umap[c] == 0 如果为0,说明不存在

遍历不是必须使用auto it

for(auto e : umap){

*************

}

发表于 2021-04-17 16:23:01 回复(0)

C/C++

codewind

#include<iostream>
#include<cstring>
#include<unordered_map>
using namespace std;

int main() {
    int n,m;cin>>n>>m;
    string a,b;
    cin>>a>>b;
    if(a.size() !=b.size()) {
        puts("false");
        return 0;
    }else {
        unordered_map<int,int> _map;
        for(char &x: a) _map[x]++;
        
        for(char &x: b) {
            if(_map.find(x) !=_map.end()) {
                _map[x]--;
            }else {
                puts("false");
                return 0;
            }
        }
        puts("true");
        
    }
    
    
    
    
    
    return 0;
}

发表于 2021-02-02 17:55:26 回复(0)

路过这座城市

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int len1 = sc.nextInt();
        int len2 = sc.nextInt();
        String x = sc.next();
        String y = sc.next();
        
        int[] num = new int[300];
        boolean temp = true;
        if(len1!=len2||x == null || y == null){
            System.out.println("false");
        }else{
            for(int i = 0;i<x.length();i++){  //不能用len1
                num[x.charAt(i)]++;
            }
            for(int i = 0;i<y.length();i++){
                num[y.charAt(i)]--;
            }
             
             for(int i=0;i<300;i++){
              if(num[i]!=0){
                 temp = false;
                 break;
              }
             }
            System.out.println(temp);
        }
    }
}

坑的地方在于

输入的两个长度相等，但输入的字符串长度其实不等

编辑于 2020-08-13 21:32:13 回复(0)

Java

码海泛舟

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static int n, m;
    static Map<Character, Integer> map1 = new HashMap<>();
    static Map<Character, Integer> map2 = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        String s1 = sc.next();
        String s2 = sc.next();
        boolean res = f(s1, s2);
        if (res) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }

    private static boolean f(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            if (map1.containsKey(c)) {
                int cnt = map1.get(c);
                map1.put(c, cnt + 1);
            } else {
                map1.put(c, 1);
            }
        }
        for (int i = 0; i < s2.length(); i++) {
            char c = s2.charAt(i);
            if (map2.containsKey(c)) {
                int cnt = map2.get(c);
                map2.put(c, cnt + 1);
            } else {
                map2.put(c, 1);
            }
        }
        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            int cnt1 = map1.get(c);
            if (!map2.containsKey(c)) return false;
            int cnt2 = map2.get(c);
            if (cnt1 != cnt2) return false;
        }
        return true;
    }
}

发表于 2020-07-06 10:29:21 回复(0)

Python

嘟嘟兔

import sys
# n, m不准确
_ = sys.stdin.readline().strip().split()
    
s1 = sys.stdin.readline().strip()
s2 = sys.stdin.readline().strip()

n = len(s1)
m = len(s2)
if n != m:
    print('false')
    exit()

# 简单哈希
count = [0] * 130
for i in range(n):
    count[ord(s1[i])] += 1
    count[ord(s2[i])] -= 1
    
for i in range(129):
    if count[i] != 0:
        print('false')
        exit()
        
print('true')

发表于 2020-06-30 11:03:27 回复(0)

杰瑞大

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(){
    int L, R;
    string L_str, R_str;
    
    cin >> L >> R;
    if(L != R)
        return false;
    vector<int> L_count(256, 0);
    vector<int> R_count(256, 0);
    cin >> L_str >> R_str;
    for(auto & c : L_str){
        L_count[c]++;
    }
    for(auto & c : R_str){
        R_count[c]++;
    }
    for(int i = 0; i < L_count.size(); i++){
        if(R_count[i] != L_count[i]){
            cout << "false";
            return 0;
        }
    }
    cout << "true";
    return 0;
}

发表于 2020-01-13 15:11:42 回复(0)

双剑华斩丨永恩

#include <stdio.h>
#include <string.h>

int main(){
    int n,m;
    char str1[100001];
    char str2[100001];

    int flag[256];


    scanf("%d %d", &n, &m);
    getchar();

    gets(str1);
    gets(str2);

    if(n!=m){
        printf("false\n");
        return 0;
    }
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int i,j,k;
    for(i = 0;i < len1;i++){
        flag[str1[i]]++;
    }
    for(j = 0;j < len2;j++){
        flag[str2[j]]--;
    }

    for(k = 0;k < 256;k++){
        if(flag[k]!=0)
        {
            printf("false\n");
            return 0;
        }
    }
    printf("true\n");

    return 0;
}

字符串的处理真是醉死我了。
字符串处理的文章，链接：https://blog.csdn.net/zqixiao_09/article/details/50189477

发表于 2019-11-25 21:08:20 回复(0)

提交观点

问题信息

模拟

上传者：小小

难度：

15条回答 7收藏 3632浏览

通过挑战的用户

查看代码

牛客14363...

2022-09-11 16:45:49
兔兔emo

2022-09-10 10:57:20
牛客16312...

2022-09-08 21:12:59
牛客96188...

2022-08-27 16:20:57
漏雨之网

2022-08-27 11:02:31

判断两个字符串是否为变形词

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题