如何判断两个String是否是Anagrams_java达成

发布时间：2021-12-10 13:52:17 所属栏目：PHP教程来源：互联网

导读：Anagrams:是颠倒字母顺序的字符串本文提供三个方法，分别分析时间空间复杂度方法一：暴力遍历时间复杂度：O(n^2) 方法二：基于排序算法，Sorting的时间复杂度是O(n*log(n))。所以先把两个字符数字进行排序，再判断。 public class CustomStringUtil { boo

Anagrams:是颠倒字母顺序的字符串

本文提供三个方法，分别分析时间空间复杂度

方法一：暴力遍历时间复杂度：O(n^2)

方法二：基于排序算法，Sorting的时间复杂度是O(n*log(n))。所以先把两个字符数字进行排序，再判断。

public class CustomStringUtil
{

  boolean firstIsAnagram(String sFirst, String sSecond)
  {
      char[] cFirstArray = sFirst.toCharArray();
      char[] cSecondArray = sFirst.toCharArray();

      Arrays.sort(cFirstArray);
      Arrays.sort(cSecondArray);

      return Arrays.equals(cFirstArray, cSecondArray);
  }
}

分析：

（1）把一个String转换成char[]，时间：O(n)，空间：O(n)（数组占用的）

（2）给数组排序：时间：O(n*log(n))，空间：O(n)

（2）比较这两个数组：时间：O(n)，空间：O(1)（可能一些临时计数器可能会用到一点空间）

总结：这个算法的时间复杂度是：O(n*log(n))

方法三：应用哈希表的思想。

首先我们知道，在ASCII Table中每个字符串对应一个整形数，这里我们就利用这一点，把这个整形数当做数组的下标，这样一个字符就对应到数组中的唯一一个位置。

算法思想：我们可以用一个数组，数组下标就是字符的索引，然后计算字符串中每个字符出现的次数。在第一个字符串中，每出现一个字符就在相应的数组位置上加一；在第二个字符串中，每出现一个字符就在数组相应的位置上减一。我们这样操作先遍历第一个字符串，再遍历第二个字符串，这两个字符串是Anagrams的唯一一种情况就是最后这个数组还是全0。就意味着这两个字符串中某一个特定的字符个数相同。

算法步骤：

（1）生成一个236位的整数数组k

（2）对于第一个字符串sFirst中的每一个字符x，x对应的整型值是y，把k[y]加1

（3）对于第二个字符串sSecond中的每一个字符x，x对应的整型值是y，把k[y]减1

（4）如果数组k仍然是全零，那么字符串sFirst和sSecond就是Anagrams

代码：

public class CustomStringUtil
{
  public static boolean secondIsAnagram(String sFirst, String sSecond)
  {
      if (sFirst.length() != sSecond.length())
      {
        return false;
      }
      int[] asciiChars = new int[256];
      for (int i = sFirst.length() - 1; i>=0; --i)
      {
        ++asciiChars[sFirst.charAt(i)]; //关键代码
      }
      for (int i = sFirst.length() - 1; i>=0; --i)
      {
        char currChar = sSecond.charAt(i);
        if (asciiChars[currChar] == 0)
        {
            return false;
        }
        --asciiChars[currChar];
      }
      return true;
  }
}

分析：时间：O(n)（遍历一次数组的时间）空间O(1)（空间不随着处理的字符串的大小而变化）

注意：这上面的代码做了一个假设：就是我们有一个确定的256个字符的集合。要注意到，这个假设对于编程来说是一个巨大的陷阱，我们应该非常小心。

（编辑：应用网_丽江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

php读取大文件最好的实	php无限遍历文件夹示例
php中实现过滤UBB代码	Laravel模板引擎Blade