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

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

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

问题

  1. public class AnagramCounter {
  2. public static void main(String[] args) {
  3. String text = "a c b c run urn urn";
  4. String word = "urn";
  5. System.out.print(countAnagrams(text, word));
  6. }
  7. static boolean areAnagrams(String s1, String s2) {
  8. char[] ch1 = s1.toCharArray();
  9. char[] ch2 = s2.toCharArray();
  10. Arrays.sort(ch1);
  11. Arrays.sort(ch2);
  12. return Arrays.equals(ch1, ch2);
  13. }
  14. static int countAnagrams(String text, String word) {
  15. int N = text.length();
  16. int n = word.length();
  17. int res = 0;
  18. for (int i = 0; i <= N - n; i++) {
  19. String s = text.substring(i, i + n);
  20. if (areAnagrams(word, s))
  21. res++;
  22. }
  23. return res;
  24. }
  25. }
英文:

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.

  1. public static void main(String[] args) {
  2. String text = &quot;a c b c run urn urn&quot;;
  3. String word = &quot;urn&quot;;
  4. System.out.print(countAnagrams(text, word));
  5. }
  6. static boolean araAnagram(String s1,
  7. String s2)
  8. {
  9. char[] ch1 = s1.toCharArray();
  10. char[] ch2 = s2.toCharArray();
  11. Arrays.sort(ch1);
  12. Arrays.sort(ch2);
  13. if (Arrays.equals(ch1, ch2))
  14. return true;
  15. else
  16. return false;
  17. }
  18. static int countAnagrams(String text, String word)
  19. {
  20. int N = text.length();
  21. int n = word.length();
  22. int res = 0;
  23. for (int i = 0; i &lt;= N - n; i++) {
  24. String s = text.substring(i, i + n);
  25. if (araAnagram(word, s))
  26. res++;
  27. }
  28. return res;
  29. }

This program does not suit with my requirement
please help.

答案1

得分: 1

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

  1. static String anagram(String s) {
  2. char[] arr = s.toCharArray();
  3. Arrays.sort(arr);
  4. return new String(arr);
  5. }
  6. static long countAnagrams(String input) {
  7. if (null == input || input.isEmpty()) {
  8. return 0;
  9. }
  10. return Arrays.stream(input.split("\\s+")) // 单词流
  11. .distinct() // 获取唯一的单词并且
  12. // 放入 Map<String, List<String>> 中,其中 List 包含输入字符串中包含的所有变位词
  13. .collect(Collectors.groupingBy(MyClass::anagram))
  14. .entrySet() //
  15. .stream() // 条目流
  16. .filter(e -> e.getValue().size() > 1) // 过滤至少有两个变位词的值
  17. .peek(e -> System.out.println(e.getValue())) // 调试打印变位词列表
  18. .count(); // 并对它们进行计数
  19. }

测试:

  1. String[] tests = {
  2. "aa aa odg dog gdo",
  3. "cars are very cool so are arcs and my os"
  4. };
  5. Arrays.stream(tests)
  6. .forEach(s -> System.out.printf("'%s' -> 变位词数量=%d%n", s, countAnagrams(s)));

输出:

  1. [odg, dog, gdo]
  2. 'aa aa odg dog gdo' -> 变位词数量=1
  3. [so, os]
  4. [cars, arcs]
  5. '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:

  1. static String anagram(String s) {
  2. char[] arr = s.toCharArray();
  3. Arrays.sort(arr);
  4. return new String(arr);
  5. }
  6. static long countAnagrams(String input) {
  7. if (null == input || input.isEmpty()) {
  8. return 0;
  9. }
  10. return Arrays.stream(input.split(&quot;\\s+&quot;)) // Stream of words
  11. .distinct() // get unique words and
  12. // move them into Map&lt;String, List&lt;String&gt;&gt;, where List contains all anagrams contained in the input string
  13. .collect(Collectors.groupingBy(MyClass::anagram))
  14. .entrySet() //
  15. .stream() // stream of entries
  16. .filter(e -&gt; e.getValue().size() &gt; 1) // filter values with at least two anagrams
  17. .peek(e -&gt; System.out.println(e.getValue())) // debug print of the anagram list
  18. .count(); // and count them
  19. }

Test:

  1. String[] tests = {
  2. &quot;aa aa odg dog gdo&quot;,
  3. &quot;cars are very cool so are arcs and my os&quot;
  4. };
  5. Arrays.stream(tests)
  6. .forEach(s -&gt; System.out.printf(&quot;&#39;%s&#39; -&gt; anagram count=%d%n&quot;, s, countAnagrams(s)));

Output

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

答案2

得分: 1

这可以解决。

  1. public static boolean anagrams(String s1, String s2){
  2. if(!(s1.equalsIgnoreCase(s2))){
  3. char[] ch1 = s1.toCharArray();
  4. char[] ch2 = s2.toCharArray();
  5. Arrays.sort(ch1);
  6. Arrays.sort(ch2);
  7. return Arrays.equals(ch1,ch2);
  8. }
  9. return false;
  10. }
  11. public static String CountingAnagrams(String str) {
  12. int res = 0;
  13. String[] splitStr = str.split("\\s+");
  14. for(int i = 0; i < splitStr.length; i++)
  15. for (int j = i + 1; j < splitStr.length; j++)
  16. if (anagrams(splitStr[i], splitStr[j]))
  17. res++;
  18. return String.valueOf(res-1);
  19. }
英文:

This can solve.

  1. public static boolean anagrams(String s1, String s2){
  2. if(!(s1.equalsIgnoreCase(s2))){
  3. char[] ch1 = s1.toCharArray();
  4. char[] ch2 = s2.toCharArray();
  5. Arrays.sort(ch1);
  6. Arrays.sort(ch2);
  7. return Arrays.equals(ch1,ch2);
  8. }
  9. return false;
  10. }
  11. public static String CountingAnagrams(String str) {
  12. int res = 0;
  13. String[] splitStr = str.split(&quot;\\s+&quot;);
  14. for(int i = 0 ; i&lt; splitStr.length; i++)
  15. for (int j = i + 1; j &lt; splitStr.length; j++)
  16. if (anagrams(splitStr[i], splitStr[j]))
  17. res++;
  18. return String.valueOf(res-1);
  19. }

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:

确定