按字母顺序排列字符串-我错过了什么明显的东西吗？

Question

public class Anagram {
    public static void main(String[] args) {

        String a = "Despera tion-".toLowerCase();
        String b = "A Rope Ends It".toLowerCase();

        String aSorted = sortStringAlphabetically(a);
        String bSorted = sortStringAlphabetically(b);

        if(aSorted.equals(bSorted)){
            System.out.println("Anagram Found!");
        }else{
            System.out.println("No anagram was found");
        }

    }

    public static String sortStringAlphabetically(String s) {

        char[] ca = s.toCharArray();
        int cnt = 0;
        ArrayList al = new ArrayList();

        for (int i = 0; i < ca.length; i++) {
            if (Character.isLetter(ca[cnt])) 
                al.add(ca[cnt]);

            cnt++;
        }

        Collections.sort(al);
        return al.toString();
    }
}

作为一个学习者，我编写了这个布尔类型的回文检查器。我的解决方案是创建一个sortStringAlphabetically方法，看起来做了太多的类型转换，即String -> chars[] -> ArrayList -> String，因为我只想比较两个字符串以测试一个短语是否是另一个短语的回文——我能否使用更少的类型转换来完成它？提示：导师的解决方案距离我的尝试相距甚远，可能出于许多原因更好，但我真的在努力掌握所有不同的集合类型。

http://www.home.hs-karlsruhe.de/~pach0003/informatik_1/aufgaben/en/doc/src-html/de/hska/java/exercises/arrays/Anagram.html#line.18

编辑

以下是原始挑战，我意识到我偏离了解决方案。

http://www.home.hs-karlsruhe.de/~pach0003/informatik_1/aufgaben/en/arrays.html

我的最初反应是简单地遍历数组a，删除与数组b匹配的字符 - 但这似乎要求我在每次迭代时重建数组 - 非常感谢您努力教育我的一切。

- Cups

---

我非常确定如果该字符串为258个字符，则教师的变位标记器将失败。 - Woot4Moo

@Woot4Moo：不会 - 但是如果字符串包含拉丁1字符集之外的任何字符，它将失败。 - Michael Borgwardt

两个注释（其实是三个）： 1）你正在尝试在方法中管理两个计数器。想一想为什么这样做以及是否需要它。 2）如果你想学习类型，请阅读有关String的文档，它具有位置索引作为方法，因此您可以避免使用数组。 2.5）你可能想专注于基本的数组解决方案。集合很棒，但它们在大多数情况下对CS课程效率低下，并且除非你从头开始编写它们，否则它们不会帮助你处理BigO。 - Daniel B. Chapman

不必创建ArrayList，可以使用Arrays.Sort()方法进行排序..!! - S2S2

@Vijay - 谢谢，是的，那是我主要的收获之一。 - Cups

Answer 1

如果您使用这个算法，有不同的方法可以改进它。 首先，您不一定需要创建一个字符数组。您可以使用String.charAt()来访问字符串中的特定字符。

其次，您不需要一个列表。如果您使用了SortedMultiSet或SortedBag，您可以按排序顺序添加元素。如果您编写一个从字符串创建SortedMultiSet的函数，您可以在不重新构建字符串的情况下比较集合。

注意：我不知道您可以使用哪些库（Google和Apache有这些类型），但您总是可以自己 'brew'。

此外，请确保为您的类型使用泛型。仅定义ArrayLists相当冒险，我认为。

- Uri

---

使用泛型-当然...我还没有立即做出这样的反应-这是我应该努力做到的。谢谢。 - Cups

Answer 2

你的算法，但更短（然而，速度较慢）。在Java的各种库类中，“类型转换”是“隐式”完成的：

public static boolean isAnagram(String a, String b) {
    List<String> listA = new ArrayList<String>(Arrays.asList(
      a.toLowerCase().replaceAll("\\W", "").split("")));
    List<String> listB = new ArrayList<String>(Arrays.asList(
      b.toLowerCase().replaceAll("\\W", "").split("")));

    Collections.sort(listA);
    Collections.sort(listB);

    return listA.equals(listB);
}

可选地，将正则表达式\W替换为排除那些不想考虑的字母的内容，以进行变位词。

- Lukas Eder

Answer 3

您可以不使用列表而对字符串进行排序：

public static String sortStringAlphabetically(String s) {
    String lettersOnly = s.replaceAll("\\W", "");
    char[] chars = lettersOnly.toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}

注意：我实际上还没有尝试运行这段代码。

- beny23

---

代码运行良好 :) - 简单多了，我没有意识到我可以如此简单地使用排序--认为它必须在从抽象列表派生的集合上完成。谢谢。 - Cups

Answer 4

public class Anagram {
    public static void main(String[] args) throws Exception {
        String s1 = "Despera tion-";
        String s2 = "A Rope Ends It";
        anagramCheck(s1, s2);
    }

    private static void anagramCheck(String s1, String s2) {
        if (isAnagram(s1, s2)) {
            System.out.println("Anagram Found!");
        } else {
            System.out.println("No anagram was found");
        }
    }

    private static boolean isAnagram(String s1, String s2) {
        return sort(s1).equals(sort(s2));
    }

    private static String sort(String s) {
        char[] array = s.replaceAll("\\W", "").toLowerCase().toCharArray();
        Arrays.sort(array);
        return new String(array);
    }
}

- Prashant Bhate