具有相同字符集的組詞


難度級別
經常問 貝萊德 思傑 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).

空間複雜度

我們正在維護一個哈希表,因此空間複雜度為 上).

參考