首页 > 试题广场 >

字符串分类

[编程题]字符串分类
  • 热度指数：3765 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
牛牛有N个字符串，他想将这些字符串分类，他认为两个字符串A和B属于同一类需要满足以下条件：
A中交换任意位置的两个字符，最终可以得到B，交换的次数不限。比如：abc与bca就是同一类字符串。
现在牛牛想知道这N个字符串可以分成几类。

输入描述:
首先输入一个正整数N（1 <= N <= 50），接下来输入N个字符串，每个字符串长度不超过50。


输出描述:
输出一个整数表示分类的个数。
示例1

输入

4
abcd
abdc
dabc
bacd

输出

1
算法知识视频讲解
添加回答
喜欢打地铺头像 喜欢打地铺 
//
//  main.cpp
//  violent_enumeration
//
//  Created by LU QI on 2017/11/06.
//  Copyright © 2017 LU QI. All rights reserved.
//

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

bool compared(string a, string b){
    if(a.length()!=b.length()) return false;
    else{
        int count=0;
        bool h=true;
        __SIZE_TYPE__ n = a.size();
        for(int i=0;i<n;i++){
            h = true;
            for(int j=0;j<n&&h;j++){
                if(b[j]==a[i]){
                    count++;
                    h = false;
                    b[j]='#';
                }
            }
        }
        if(count == n) return true;
        else return false;
    }
}
int main(int argc, const char * argv[]) {
    int N;
    cin>>N;
    string array[N];
    int count=N;
    for(int i=0;i<N;i++){
        cin>>array[i];
    }
    for(int i=0;i<N-1;i++){
        if(array[i]!="#"){
            for(int j= i+1; j<N; j++){
                if(array[j]!="#"){
                    if(compared(array[i], array[j])){
                        count--;
                        array[j]="#";
                    }
                }
            }
        }
    }
    cout<<count<<endl;
    return 0;
}

发表于 2017-11-07 19:08:43 回复(0)
更多回答
yuan121头像 yuan121 
public class Main
{
	public static void main(String[] args) 
	{
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		HashSet<String> set = new HashSet<String>();
		while(n!=0)
		{
			char[] array = scanner.next().toCharArray();
			Arrays.sort(array);
			set.add(String.valueOf(array));
			n--;
		}
        scanner.close();
		System.out.println(set.size());
	}
}

编辑于 2017-03-25 10:50:09 回复(0)
牛客688790号头像 牛客688790号 
#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
	map<string, size_t> Maps;
	for (size_t i = 0; i < n; i++)
	{
		string current;
		cin >> current;
		sort(current.begin(), current.end());
		Maps[current]++;
	}
	cout << Maps.size() << endl;
	return 0;
}
利用map中唯一键值，来统计排序后的字符串个数。
编辑于 2017-03-24 17:58:43 回复(1)
飞201909171602337头像 飞201909171602337 
str_list=[]
N=int(input()) for i in range(N):
    str_list.append(''.join(sorted(input()))) print(len(set(str_list)))

发表于 2019-10-08 12:11:34 回复(0)
Jax201903221357986头像 Jax201903221357986
其实就是按字母排序后去重复，可用set或者list去重，上面都写的set我改了一个list的。
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        List<String> list = new LinkedList<String>();
        List<String> list1 = new LinkedList<String>();
        for (int i = 0; i < num; i++) {
            String aa = sc.next();
            list.add(aa);
        }
        for (String string : list) {
            char[] ch = string.toCharArray();
            Arrays.sort(ch);
            if(!list1.contains(String.valueOf(ch))) {
                list1.add(String.valueOf(ch));
            }
        }
        System.out.println(list1.size());
    }
}


发表于 2019-03-25 17:36:32 回复(0)
Energy201901080933545头像 Energy201901080933545 
package com.heima.schedule.test;

import org.checkerframework.checker.units.qual.min;

import java.util.Scanner;


public class Test02 {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        char[][] arr = new char[num][];
        for (int i = 0; i < num; i++) {
            arr[i] = in.next().toCharArray();
            sort(arr[i]);
        }

        char[][] s = new char[num][];
        s[0] = arr[0];
        int resultLen = 1;

        for (int i = 1; i < num; i++) {
            boolean flag = false;
            for (int j = 0; j < resultLen; j++){
                // 比较
                if (ifSame(s[j], arr[i])){
                    flag = true;
                    break;
                }
            }
            if (! flag) {
                s[resultLen++] = arr[i];
            }
        }

        System.out.println(resultLen);
    }

    /**
     * 判断两个字符数组是否相同
     * @param c1
     * @param c2
     * @return
     */
    private static boolean ifSame(char[] c1, char[] c2) {
        if (c1.length != c2.length) {
            return false;
        }
        for (int i = 0; i < c1.length; i++) {
            if (c1[i] != c2[i]) {
                return false;
            }
        }

        return true;
    }

    /**
     * 字符排序
     * @param chars
     */
    private static void sort(char[] chars){
        for (int i = 0; i < chars.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[j] < chars[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                char temp = chars[i];
                chars[i] = chars[minIndex];
                chars[minIndex] = temp;
            }
        }
    }


}

发表于 2023-08-19 15:30:02 回复(0)
Python
牛客882774523号头像 牛客882774523号
i = 0
N = int(input())
str_line = []
while True:
    word = input()
    str_line.append(word)
    i = i + 1
    if i == N:
        break
for j in range (len(str_line)):
    str_line[j] = ''.join(sorted(str_line[j]))
print(len(set(str_line)))



发表于 2022-04-11 17:45:38 回复(0)
牛客511771125号头像 牛客511771125号 
#include<iostream>
(720)#include<cstring>
#include<cmath>
(808)#include<algorithm>
#include<iomanip>
using namespace std;

int main()
{
	int a[55][27] = { 0 };
	for (int i = 0; i < 55; i++)
		for (int j = 0; j < 27; j++)
			a[i][j] = 0;
	int count = 0;
	int n;
	cin >> n;
	string str[55];
	for (int i = 0; i < n; i++)
	{
		cin >> str[i];
	}
	for (int i = 0; i < n; i++)
	{
		int len = str[i].length();
		for (int j = 0; j < len; j++)
		{
			a[i][str[i][j] - 97]++;
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (a[i][0] == 50 + i)
			continue;
		count++;
		for (int j = i + 1; j < n; j++)
		{
			int flag = 1;
			for (int k = 0; k < 26; k++)
			{
				if (a[i][k] != a[j][k])
					flag = 0;
			}
			if (flag == 1)
			{
				a[j][0] = 50 + j;
			}
		}
	}
	cout << count;
}

发表于 2020-04-03 21:00:32 回复(0)
JavaScript
江村暮头像 江村暮 
const main = (strings) => {
    var types = [];
    for(let i = 0; i < strings.length; i++){
        //let str = strings[i].split('').sort().join('');
        let str = strings[i].split('').sort((item1, item2)=>{
            return item1.localeCompare(item2, 'zh-CN');
        }).join(''); //适配中文
        if(!types.includes(str))types.push(str)      
    }
    return types.length
}

console.log(main(['东京', '京东']))// expect 1

发表于 2020-03-21 18:47:42 回复(0)
nooBiee头像 nooBiee 
import sys
 
try:
    while True:
        n = int(input())
        t = list()
        for i in range(n):
            t.append(input())
        S = []
        for i in t:
            isum = dict()
            a = list(set(i))
            for j in range(len(a)):
                isum[a[j]] = i.count(a[j])
            if isum not in S:
                S.append(isum)
        print(len(S))
except:
    pass

发表于 2020-03-19 22:33:35 回复(0)
HANABI201905082259733头像 HANABI201905082259733
用的js

var N
var obj={}
var arr1=[]
  N =readline()
for (let i=0; i<N; i++) {
  var c=readline()
 var temp=[]
        for(z=0;z<c.length;z++){
            temp.push(c[z])
        }
        var arr=temp.sort()
        var str=''
        for(j=0;j<arr.length;j++){
            str=str+arr[j]
        }
        if(!obj[str]){
  obj[str]=1
  }else{
      obj[str]++
  }
  }
    for(var key in obj){
        arr1.push(obj[key])
    }
    var a=arr1.length
print(a)

发表于 2019-08-25 11:54:46 回复(0)
进步不断头像 进步不断
python解法：排序再比较
发表于 2018-07-19 01:01:21 回复(0)
C/C++
7368696E69616E头像 7368696E69616E
/*纯C语言实现*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void sort(char* str){
    int max;
    int temp;
    int length = strlen(str);
    for (int i = 0; i < length; i++){
        max = str[0];
        temp = 0;
        int j;
        for ( j= 1; j<length - i; j++){
            if (max < str[j]){
                max = str[j];
                temp = j;
            }
        }
        if (max != str[j - 1]){
            str[temp] = str[j-1];
            str[j-1] = max;
        }
    }
}

int main(){
    int num;
    char(*str)[50];
    scanf("%d", &num);
    int i = 0;
    str = (char(*)[50])malloc(num* 50);
    while (num - i>0){
        scanf("%s", str[i]);
        sort(str[i++]);;
    }

    int* flag = (int*)malloc(sizeof(int)*num);
    int ret = 0;
    memset(flag,0,num*sizeof(int));
    int k = 0;
    while (k < num){
        if (flag[k] == 0){
            for (int j = 1; j < num; j++){
                if (strcmp(str[k], str[j]) == 0 && flag[j] != 1){
                    flag[k] = 1;
                    flag[j] = 1;
                }
            }
            ret++;
        }
        k++;
    }
    printf("%d",ret);
    free(str);
    free(flag);
    str = NULL;
    flag = NULL;
    getchar();
    return 0;
}


发表于 2018-03-04 18:29:29 回复(0)
Java
丶Vanes头像 丶Vanes 
import java.util.*;
public class StringClassify {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String[] str = new String[N];
        HashSet set = new HashSet();
        for (int i = 0; i < N; i++) {
            str[i] = sortStr(sc.next());
            set.add(str[i]);
        }
        System.out.println(set.size());
    }
    public static String sortStr(String str) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }
}
编辑于 2017-11-16 15:36:31 回复(0)
牛客375006号头像 牛客375006号

这是一个高效的方案。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring> //牛客网环境下string操作函数需要引用这个库
using namespace std;

void sortStr(string &str) {
    for (int i = 0; i < (int)str.size() - 1; i++) {
        for (int j = (int)str.size() - 1; j > 0; j--) {
            if (str[j - 1] > str[j]) {
                char temp = str[j];
                str[j] = str[j - 1];
                str[j - 1] = temp;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    int n;
    cin>>n;
    int count = n;
    string str[50];
    for (int i = 0; i < n; i++) {
        cin>>str[i];
        sortStr(str[i]);
    }
    sort(str, str + n);
    int i = 0;
    while (i < n - 1) {
        int j;
        for (j = n - 1; j > i; j--) {
            char a[50], b[50];
            strcpy(a, str[i].c_str());
            strcpy(b, str[j].c_str());
            if (!strcmp(a, b)){
                count -= j - i;
                i = j + 1;
                break;
            }
        }
        if (i != j + 1) {
            i++;
        }
    }
    cout<<count;
    return 0;
}
发表于 2017-10-19 14:33:38 回复(0)
HudsonAndroid头像 HudsonAndroid
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args){
        checkCategoryNumber();
    }
    
    /**
     * 查看有几类字母
     * 同一类的字符串调换任意顺序可变成本类中其他成员。说白了就是字符类型相同
     */
    private static void checkCategoryNumber(){
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        List<String> strs = new ArrayList<String>();
        for(int i =0;i<count;i++){
            String str = scanner.next();
            char[] array = str.toCharArray();
            Arrays.sort(array);
            str = String.copyValueOf(array);
            strs.add(str);
        }
        HashSet<String> set = new HashSet<String>();
        set.addAll(strs);
        System.out.println(set.size());
        scanner.close();
    }
}

发表于 2017-10-11 11:43:21 回复(0)
异想难寻头像 异想难寻
最笨的方法： 
#include<iostream>
#include <string.h>
using namespace std;

int* chartoint(char *ch)
{
    int size=strlen(ch);
    int* ret = new int[size];
    for(int i=0;i<size;i++)
    {
        ret[i] = ch[i];
    }
    return ret;
}
char *sort(char*ch)
{
    for(int i=0;i<strlen(ch)-1;i++)
        for(int j=0;j<strlen(ch)-1-i;j++)
        {
            if(chartoint(ch)[j]>chartoint(ch)[j+1])
            {
                char ch1 = ch[j];
                ch[j] = ch[j+1];
                ch[j+1] = ch1;
            }
        }
    
    return ch;
}

bool boolequal(char*ch1,char*ch2)
{
    if(strlen(ch1)!=strlen(ch2))
        return 0;
    for(int i=0;i<strlen(ch1);i++)
    {
        if(ch1[i]!=ch2[i])
            return 0;
    }
    return 1;
}

int main()
{
    int n,ret=1;
    cin >> n;
    char ch[n][50];
    char newch[50][50];
    for(int i=0;i<n;i++)
        cin >> ch[i];
    for(int i=1;i<n;i++)
    {
        for(int j=i-1;j>=0;j--)
        {
            if(boolequal(sort(ch[j]),sort(ch[i])))
                break;
            if(j==0)
                ret ++;
        }
    }
    cout<<ret;
    
}

发表于 2017-09-01 15:10:08 回复(0)
南邮kd头像 南邮kd 
import java.util.*;
public class Main{
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		TreeSet <String> tree=new TreeSet<String>();
		while(sc.hasNext()){
			int num=sc.nextInt();
			int i=0;
			while(i<num){
				char ch[]=sc.next().toCharArray();
				Arrays.sort(ch);
				tree.add(String.valueOf(ch));
				i++;
			}
			System.out.println(tree.size());
		}
		sc.close();
	}
}

发表于 2017-08-23 11:11:27 回复(0)
Java
victor_头像 victor_
import java.util.*;
public class StringClassify{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int num=in.nextInt();
        in.nextLine();
        String[] strs=new String[num];
        for(int i=0;i<num;i++){
            strs[i]=in.nextLine();
        }
        int result=numberOfClassStr(strs);
        System.out.println(result);
        
    }
    public static int numberOfClassStr(String[] strs){
     
        List<String[]> list=new ArrayList<String[]>();
        for(int i=0;i<strs.length;i++){
             String[] ss=strs[i].split("");
             Arrays.sort(ss);
             if(!contain(list,ss)){
                 list.add(ss);
             }
        }
        return list.size();
    }
    
    public static boolean contain(List<String[]> list,String[] ss){
        for(int i=0;i<list.size();i++){
            String[] tmp=list.get(i);
            if(tmp.length==ss.length){
                int j=0;
                for(j=0;j<ss.length;j++){
                    if(!ss[j].equals(tmp[j])){
                        break;
                    }
                }
                if(j==ss.length){
                    return true;
                }
            }else{
                continue;
            }
        }
        return false;
    }
}

发表于 2017-05-09 20:10:29 回复(2)
Jimmy_gg头像 Jimmy_gg 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main()
{
	using namespace std;
	int n;
	while (cin >> n) {
		vector<string> str(n);
		for (int i = 0; i < n; i++)
			cin >> str[i];
		int ans = 0;
		for (int i = 0; i < n; i++) {
			int index[127] = { 0 };
			string temp_str = "";
			if (str[i] != "") {
				temp_str = str[i];
				for (int j = 0; j < str[i].size(); j++) {
					index[str[i][j]] ++;
				}
				ans++;
			}
			else {
				continue;
			}
			for (int j = i; j < n; j++) {
				if (str[j] != "" && str[j].size() == temp_str.size()) {
					int temp[127] = { 0 };
					for (int k = 0; k < str[j].size(); k++) {
						temp[str[j][k]] ++;
					}
					int k = 0;
					for (k = 0; k < 127; k++) {
						if (index[k] != temp[k])
							break;
					}
					if (k == 127) {
						str[j] = "";
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

发表于 2017-04-21 16:24:46 回复(0)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 字符串 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 模拟 测试开发工程师 大数据开发工程师 Java工程师 牛客
来自：【2017】牛客模考（...
难度：
31条回答 11257浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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