zl程序教程

您现在的位置是:首页 >  其他

当前栏目

数组的包含

2023-03-14 09:45:30 时间

题目:输入两个字符串str1和str2,请判断str1中所有字符是否都存在于str2中(大众点评笔试题)。

思路:一看这题目很容易想到暴力破解,不过这样的话效率是很低的,消耗的时间为s1.length*s2.length。那我们可以先对s2进行排序然后二分查找,这样的话时间复杂度就会降低到s1.length*lgN级别。不要小看N的lgN的差距,当数据量达到很大的时候,他们之间的时间差距会非常大。

代码:

public static boolean check(String s1, String s2) {
    char[] s2_arr = s2.toCharArray();
    Arrays.sort(s2_arr);
    for (int i = 0; i < s1.length(); i++) {
      char a = s1.charAt(i);
      int index = Arrays.binarySearch(s2_arr, a);
      if (index < 0)
        return false;
    }
    return true;
  }