如何在Java中编写计算变位词出现次数的算法?

huangapple go评论66阅读模式
英文:

How to write algorithm for Count Occurrences of Anagrams in java?

问题

public class AnagramCounter {

    public static void main(String[] args) {
        String text = "a c b c run urn urn";
        String word = "urn";
        System.out.print(countAnagrams(text, word));

    }

    static boolean areAnagrams(String s1, String s2) {
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        Arrays.sort(ch1);
        Arrays.sort(ch2);
        return Arrays.equals(ch1, ch2);
    }

    static int countAnagrams(String text, String word) {
        int N = text.length();
        int n = word.length();
        int res = 0;
        for (int i = 0; i <= N - n; i++) {
            String s = text.substring(i, i + n);
            if (areAnagrams(word, s))
                res++;
        }
        return res;
    }
}
英文:

Hi I want to write anagram algorithm in java. My requirement is if someone gave a string like this

Input: &quot;aa aa odg dog gdo&quot; its count of anagram count should be 2. Can anyone help me to fix this?
I have tried a solution but it is nit working.

public static void main(String[] args) {
        String text = &quot;a c b c run urn urn&quot;;
        String word = &quot;urn&quot;;
        System.out.print(countAnagrams(text, word));

    }

    static boolean araAnagram(String s1,
                              String s2)
    {
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        Arrays.sort(ch1);
        Arrays.sort(ch2);
        if (Arrays.equals(ch1, ch2))
            return true;
        else
            return false;
    }

    static int countAnagrams(String text, String word)
    {
        int N = text.length();
        int n = word.length();
        int res = 0;
        for (int i = 0; i &lt;= N - n; i++) {

            String s = text.substring(i, i + n);
            if (araAnagram(word, s))
                res++;
        }
        return res;
    }

This program does not suit with my requirement
please help.

答案1

得分: 1

假设有一种方法可以将一个单词转换为有序字符序列,可以使用 Stream API 计算变位词的数量:

static String anagram(String s) {
    char[] arr = s.toCharArray();
    Arrays.sort(arr);
    return new String(arr);
}

static long countAnagrams(String input) {
    if (null == input || input.isEmpty()) {
        return 0;
    }
    return Arrays.stream(input.split("\\s+"))  // 单词流
            .distinct()  // 获取唯一的单词并且
            // 放入 Map<String, List<String>> 中,其中 List 包含输入字符串中包含的所有变位词
            .collect(Collectors.groupingBy(MyClass::anagram)) 
            .entrySet() // 
            .stream()   // 条目流 
            .filter(e -> e.getValue().size() > 1) // 过滤至少有两个变位词的值
            .peek(e -> System.out.println(e.getValue())) // 调试打印变位词列表
            .count(); // 并对它们进行计数
}

测试:

String[] tests = {
    "aa aa odg dog gdo",
    "cars are very cool so are arcs and my os"
};

Arrays.stream(tests)
      .forEach(s -> System.out.printf("'%s' -> 变位词数量=%d%n", s, countAnagrams(s)));

输出:

[odg, dog, gdo]
'aa aa odg dog gdo' -> 变位词数量=1
[so, os]
[cars, arcs]
'cars are very cool so are arcs and my os' -> 变位词数量=2
英文:

Assuming that there is a method to convert a word into an ordered sequence of characters, the number of anagrams may be calculated using Stream API:

static String anagram(String s) {
    char[] arr = s.toCharArray();
    Arrays.sort(arr);
    return new String(arr);
}

static long countAnagrams(String input) {
    if (null == input || input.isEmpty()) {
        return 0;
    }
    return Arrays.stream(input.split(&quot;\\s+&quot;))  // Stream of words
            .distinct()  // get unique words and
            // move them into Map&lt;String, List&lt;String&gt;&gt;, where List contains all anagrams contained in the input string
            .collect(Collectors.groupingBy(MyClass::anagram)) 
            .entrySet() // 
            .stream()   // stream of entries 
            .filter(e -&gt; e.getValue().size() &gt; 1) // filter values with at least two anagrams
            .peek(e -&gt; System.out.println(e.getValue())) // debug print of the anagram list
            .count(); // and count them
}

Test:

String[] tests = {
    &quot;aa aa odg dog gdo&quot;,
    &quot;cars are very cool so are arcs and my os&quot;
};

Arrays.stream(tests)
      .forEach(s -&gt; System.out.printf(&quot;&#39;%s&#39; -&gt; anagram count=%d%n&quot;, s, countAnagrams(s)));

Output

[odg, dog, gdo]
&#39;aa aa odg dog gdo&#39; -&gt; anagram count=1
[so, os]
[cars, arcs]
&#39;cars are very cool so are arcs and my os&#39; -&gt; anagram count=2

答案2

得分: 1

这可以解决。

public static boolean anagrams(String s1, String s2){
    if(!(s1.equalsIgnoreCase(s2))){
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        Arrays.sort(ch1);
        Arrays.sort(ch2);
        return Arrays.equals(ch1,ch2);
    }
    return false;
}

public static String CountingAnagrams(String str) {
    int res = 0;
    String[] splitStr = str.split("\\s+");
    for(int i = 0; i < splitStr.length; i++)
        for (int j = i + 1; j < splitStr.length; j++)
            if (anagrams(splitStr[i], splitStr[j]))
                res++;
    return String.valueOf(res-1);
}
英文:

This can solve.

public static boolean anagrams(String s1, String s2){
    if(!(s1.equalsIgnoreCase(s2))){
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        Arrays.sort(ch1);
        Arrays.sort(ch2);
        return Arrays.equals(ch1,ch2);
    }
    return false;
}

public static String CountingAnagrams(String str) {
    int res = 0;
    String[] splitStr = str.split(&quot;\\s+&quot;);
    for(int i = 0 ; i&lt; splitStr.length; i++)
        for (int j = i + 1; j &lt; splitStr.length; j++)
            if (anagrams(splitStr[i], splitStr[j]))
                res++;
    return String.valueOf(res-1);
}

huangapple
  • 本文由 发表于 2020年10月24日 23:33:57
  • 转载请务必保留本文链接:https://go.coder-hub.com/64515090.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定