4

如何对带有字谜的字符串数组进行排序？

例如：

输入{神，狗，abc，出租车，人}
输出{abc，出租车，狗，神，人}

我的方法：在 O(nlogn) 中对数组进行排序（不考虑字谜的情况）。接下来，拿起第一个字符串并为字符串创建一个直方图，并将直方图与数组中剩余的字符串直方图进行比较，并将匹配的字符串放在数组的适当位置..重复直到达到数组大小..这个算法采用 O(n^3) 的最坏情况（如果我们假设在最坏的情况下，每个字符串的大小也为 n）和直方图表示的额外空间

来自参考的直方图方法： 查找两个单词是否是彼此的字谜

我们能做得比这更好吗？

4

9 回答 9

13

您当然可以做得更好，如下所示：

  1. 循环遍历字符串数组
  2. 对于每个字符串，首先对其字符进行排序，将排序后的字符串作为键，将原始字符串作为值，放入哈希表中。你最终会得到一个哈希表，其中键是排序的字符串，值都是字谜，同时，这些值是有序的。您可以map<string, set<string> >为此目的服务。
  3. 遍历哈希表并将给定键的所有字谜一起输出，它们应该彼此相邻

假设字符串的长度为 M，数组的大小为 N，则时间复杂度为：O(NMlogM)，M 通常平均小于 N。所以这比你说的要有效得多。

于 2013-03-20T04:55:40.057 回答
3 
#include <vector>
#include <unordered_map>
#include <string>
#include <set>
#include <algorithm>
#include <iostream>

using namespace std;

vector<string> sort_string_anagram(vector<string> array)
{
    unordered_map<string, set<string>> anagram;

    for(string word : array)
    {
      string sorted_word(word);

      sort(sorted_word.begin(),sorted_word.end());

      anagram[sorted_word].insert(word);
    }

    sort(array.begin(), array.end());

    vector<string> result;

    for(string word : array)
    {
        unordered_map<string,set<string>>::iterator iter;

        string sorted_word(word);

        sort(sorted_word.begin(), sorted_word.end());

        if( (iter = anagram.find(sorted_word)) != anagram.end() )
        {
           for(set<string>::iterator it = (iter->second).begin(); it!= (iter->second).end();++it)
           {
              result.push_back(*it);
           }
           anagram.erase(iter);
        }
    }
    return result;
}

@Jitendard，@taocp，具有时间复杂度的完整解决方案：O( N(MlogM) + NlogN + N(MlogM + A) )。N 是数组大小，M 是单词大小，A 是单词存在的最大字谜数

于 2016-04-23T22:05:35.470 回答
2

在 python 中，这可以通过以下方式完成：

sorted(word_list, key=lambda word: ''.join(sorted(word.replace(" ", "").lower())))

其中键是按字母顺序排序的字符。字谜的关键是相同的，从而将它们保持在一起

于 2014-09-07T03:00:29.737 回答
1

@Song Wang：甚至我都在考虑这样做。但是，一旦将字符串从 hashmap 中取出，您怎么知道放置字符串的顺序？假设您提取
K1 = "abc", V1 = "cab"
K2 = "abc", V2 = "abc"
您如何知道将哪个放在列表 1 或 2 的首位？
也许你会再次对它们进行排序。但是，那么这对复杂性不利。

于 2013-03-20T07:00:42.347 回答
0

为什么要先排序？您不能仅根据字谜将数组划分为子集。对子集进行排序，最后根据每个子集中的第一个词进行合并。

于 2013-03-20T04:32:11.970 回答
0

把它放在一个'真正的'java编程上下文中（即我们使用一些现有的和基本的jdk util类，我认为下面的方法可能会给这个主题带来另一个有趣的方面（即“如何对一个字符串数组进行排序，每个字符串旁边都有字谜其他”）：

(a) 我们定义了一个比较器来判断两个字符串是否是字谜；(b) 我们使用 Arrays.sort(array,comparator) 对数组进行排序；

下面是代码和结果（这个想法可以在第 9 章看到，例如 Gayle Laakmann 的“破解编码面试”）

import java.util.Arrays;
import java.util.Comparator;

public class SolutionForSortArraysByAnagrams {

    public static void main(String[] args){

        String[] strArray = new String[]{"abets","mates","baste","meats", "betas","beast", "steam", "tames", "beats", "teams"}; 

        sortArraysByAnagrams(strArray);

        for(String str : strArray){
            System.out.println(str);
        }

    }

    private static void sortArraysByAnagrams(String[] strArray) {

        Arrays.sort(strArray, new AnagramComparator());

    }

}


class AnagramComparator implements Comparator<String> {

    @Override
    public int compare(String s1, String s2) {

        //check edge conditions and length
        if( s1 == null || s2 == null)
            return -1;
        if( s1.length() <  s2.length())
            return -1;
        else if ( s1.length() >  s2.length())
            return 1;

        //sort s1 and s2 to compare:
        //System.out.println(s1 + " vs  " + s2);        
        return sort(s1).compareTo(sort(s2));

    }

    private String sort(String s1) {
        char[] cArray = s1.toCharArray();
        Arrays.sort(cArray);        
        //System.out.println(" sorted:  " + new String(cArray));
        return new String(cArray);
    }


}

输入：{“abets”、“mates”、“baste”、“meats”、“betas”、“beast”、“steam”、“tames”、“beats”、“teams”}；

输出： abets baste betas 野兽击败伙伴肉类蒸汽驯服团队

于 2015-05-28T20:54:03.870 回答
0

从网上找到解决方案：

public static void sortStringWithAnagrams(String[] stringArray) {
    Arrays.sort(stringArray, new AnagramComparator());
}

public static class AnagramComparator implements Comparator<String> {

    public String getSortedString(String s) {
        char[] content = s.toCharArray();
        Arrays.sort(content);
        return new String(content);
    }

    public int compare(String s1, String s2) {
        return getSortedString(s1).compareTo(getSortedString(s2));
    }

}
于 2016-11-26T12:00:07.997 回答
0 
 private static String[] getSortedAnagram(String[] array) {
    Map<String, ArrayList<String>> sortedMap = new HashMap<>();
    for (String a : array) {
        String sortedString = a.chars().sorted().
                collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();
        sortedMap.computeIfAbsent(sortedString, s->new ArrayList<>()).add(a);
    }
   String[] output = new String[array.length];
   List<String> list = sortedMap.values().stream().flatMap(List::stream).collect(Collectors.toList());
   return list.toArray(output);
}
于 2019-10-22T15:12:19.173 回答
0 
import java.util.Arrays;
import java.util.Comparator;

/**
 * Sort an array of strings so that all anagrams are next to each other
 * @author asharda
 *
 */
public class Anagram implements Comparator<String> {


  public static String  anagram(String input)
  {
    char []s=input.toCharArray();
    Arrays.sort(s);
    return new String(s);
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub

    String arr[]= {"abc","god","cab","dog"};
    Arrays.sort(arr, new Anagram());
    for(String s:arr)
    System.out.println(s);

  }
  @Override
  public int compare(String arg0, String arg1) {
    return arg0.compareTo(arg1);
  }


}

//Credit to Cracking Coding Interview by Gayle Laakmann
于 2018-04-27T00:52:03.803 回答