具有相同字符集的组词


难度级别 中等
经常问 贝莱德 思杰 IBM JP摩根 SAP实验室 Xome
哈希

在具有相同字符集的组词问题中,我们给出了小写词的列表。 实现一个功能以查找具有相同唯一字符集的所有单词。

使用案列

输入

单词[] = {“可能”,“学生”,“学生”,“狗”,“学生”,“神”,“猫”,“行为”,“标签”,“蝙蝠”,“流”,“狼”,“小羊”,“艾米”,“山药”,“香脂”,“圈状”,“贵宾犬”}

输出

可能,艾米,山药,

学生们,学生们,

狗,神,

猫,演戏,

标签,蝙蝠,

流,狼,

羔羊香脂,

圈状,贵宾犬

方法1:蛮力

大意

对于每个单词,我们将遍历所有单词并找到具有相同字符集的单词,然后将其打印出来。

我们已经打印的单词,我们将对其进行标记,以免再次打印它们。

的算法 具有相同字符集的组词

  1. 对0到n-1的I进行循环
    1. 如果单词[i]的长度相等,请跳过它,因为我们已经打印了它。
    2. 创建一个数组charSet1,该数组将存储word [i]中存在的字符。
    3. 在I到n-1的范围内为j运行循环
      1. 制作一个数组charSet2,该数组将存储单词中出现的字符[j]
      2. 如果charSet1等于charSet2,则打印word [j]并将word [j]更改为空字符串,这表示我们已经打印了该字符串。
    4. 返回

具有相同字符集的组词的实现

C ++程序

#include<bits/stdc++.h>
using namespace std;
void wordsWithSameSetOfchar(vector<string>& words)
{
    int n=words.size();
    for(int i=0;i<n;i++)
    {
        if(words[i].length()==0)
        {
            continue;
        }
        vector<bool> charSet1(26,false);
        for(auto ele:words[i])
        {
            charSet1[ele-'a']=true;
        }
        for(int j=i;j<n;j++)
        {
            vector<bool> charSet2(26,false);
            for(auto ele:words[j])
            {
                charSet2[ele-'a']=true;
            }
            if(charSet2==charSet1)
            {
                cout<<words[j]<<", ";
                words[j]="";
            }
        }
        cout<<endl;
    }
    return;
}
int main()
{
    vector<string> words={ "may", "student", "students", "dog","studentssess", "god", "cat", "act","tab", "bat", "flow", "wolf", "lambs","amy", "yam", "balms", "looped", "poodle"};
    wordsWithSameSetOfchar(words);    
    return 0;
}
may, amy, yam, 
student, students, studentssess, 
dog, god, 
cat, act, 
tab, bat, 
flow, wolf, 
lambs, balms, 
looped, poodle, 

JAVA程序

import java.util.*;
public class Main
{
    static void wordsWithSameSetOfchar(String words[])
    {
        int n=words.length;
        for(int i=0;i<n;i++)
        {
            if(words[i].length()==0)
            {
                continue;
            }
            boolean[] charSet1 = new boolean[26];
            for(int l=0;l<words[i].length();l++)
            {
                charSet1[words[i].charAt(l)-'a']=true;
            }
            for(int j=i;j<n;j++)
            {
                boolean[] charSet2 = new boolean[26];
                for(int l=0;l<words[j].length();l++)
                {
                    charSet2[words[j].charAt(l)-'a']=true;
                }
                if(Arrays.equals(charSet2,charSet1))
                {
                    System.out.print(words[j]+", ");
                    words[j]="";
                }
            }
            System.out.println();
        }
        return;
    }
  public static void main(String[] args) {
    String words[]={ "may", "student", "students", "dog","studentssess", "god", "cat", "act","tab", "bat", "flow", "wolf", "lambs","amy", "yam", "balms", "looped", "poodle"};
    wordsWithSameSetOfchar(words);
  }
}
may, amy, yam, 
student, students, studentssess, 
dog, god, 
cat, act, 
tab, bat, 
flow, wolf, 
lambs, balms, 
looped, poodle,

复杂度分析

时间复杂度

我们使用了三个嵌套循环,其中两个嵌套循环的大小为N,第三个嵌套循环的大小为字符串的长度。 如果我们将字符串的长度设为L,则总时间复杂度为 O(N * N * L).

空间复杂度

我们没有使用任何多余的空间,因此空间复杂度为 O(1)。

方法2:使用哈希

大意

我们将为每个人打造一把钥匙 绳子 它将以排序的方式存储字符串的所有不同字符。 之后,我们将对具有相同键的所有单词使用散列,并将最后打印出来。

具有相同字符集的组词算法

  1. 声明一个hash_table,它将存储具有相同键的所有单词的所有索引。
  2. 创建一个函数makeKey,该函数将返回字符串的键。
  3. 对0到n-1的I进行循环
    1. 在hash_table中插入I作为'words [i]'的键。
  4. 遍历哈希表,并使用相同的键打印字符串。
  5. 返回

举例说明

单词= {“可能”,“学生”,“学生”,“狗”,“学生”,“神”,“猫”,“行为”,“标签”,“蝙蝠”,“流”,“狼” ,“小羊”,“ amy”,“山药”,“香脂”,“圈状”,“贵宾犬”}

哈希表将如下所示:

具有相同字符集的组词

具有相同字符集的组词的实现

C ++程序

#include<bits/stdc++.h>
using namespace std;
string makeKey(string& word)
{
    string key;
    vector<bool> charSet(26,false);
    for(auto ele:word)
    {
        charSet[ele-'a']=true;
    }
    for(int i=0;i<26;i++)
    {
        if(charSet[i])
        {
            key+=(char)(i+'a');
        }
    }
    return key;
}
void wordsWithSameSetOfchar(vector<string>& words)
{
    int n=words.size();
    unordered_map<string,vector<int>> hash_table;
    for(int i=0;i<n;i++)
    {
        hash_table[makeKey(words[i])].push_back(i);
    }
    for(auto keys:hash_table)
    {
        for(auto index:keys.second)
        {
            cout<<words[index]<<", ";
        }
        cout<<endl;
    }
    return;
}
int main()
{
        vector<string> words={ "may", "student", "students", "dog","studentssess", "god", "cat", "act","tab", "bat", "flow", "wolf", "lambs","amy", "yam", "balms", "looped", "poodle"};
    wordsWithSameSetOfchar(words);    
    return 0;
}
looped, poodle, 
student, students, studentssess, 
may, amy, yam, 
dog, god, 
cat, act, 
tab, bat, 
lambs, balms, 
flow, wolf,

JAVA程序

import java.util.*;
import java.util.Map.Entry; 
public class Main
{
    static String makekey(String word)
    {
        boolean[] charSet = new boolean[26];
        for(int l=0;l<word.length();l++)
        {
            charSet[word.charAt(l)-'a']=true;
        }
        String key="";
        for(int i=0;i<26;i++)
        {
            if(charSet[i])
            {
                key+=(char)(i+'a');
            }
        }
        return key;
    }
    static void wordsWithSameSetOfchar(String words[])
    {
        int n=words.length;
        HashMap<String, ArrayList<Integer>> hash_table = new HashMap<>(); 
    for (int i=0; i<n; i++) 
    { 
      String key = makekey(words[i]); 
      if(hash_table.containsKey(key)) 
      { 
        ArrayList<Integer> temp = hash_table.get(key); 
        temp.add(i); 
        hash_table.put(key, temp); 
      } 
      else
      { 
        ArrayList<Integer> temp = new ArrayList<>(); 
        temp.add(i); 
        hash_table.put(key, temp); 
      } 
    } 
    for (Entry<String, ArrayList<Integer>> keys : hash_table.entrySet()) 
    { 
      ArrayList<Integer> indices =keys.getValue(); 
      for (Integer index:indices) 
        System.out.print( words[index] + ", "); 
      System.out.println(); 
    } 
        return;
    }
  public static void main(String[] args) {
    String words[]={ "may", "student", "students", "dog","studentssess", "god", "cat", "act","tab", "bat", "flow", "wolf", "lambs","amy", "yam", "balms", "looped", "poodle"};
    wordsWithSameSetOfchar(words);
  }
}
student, students, studentssess, 
tab, bat, 
cat, act, 
lambs, balms, 
may, amy, yam, 
looped, poodle, 
dog, god, 
flow, wolf,

复杂度分析

时间复杂度

我们只对数组进行一次迭代,并且在每次迭代中,我们都通过对字符串进行迭代来生成密钥。 因此,如果我们将字符串的长度设为L,则总时间复杂度为 O(N * L).

空间复杂度

我们正在维护一个哈希表,因此空间复杂度为 上).

參考資料