A.每日一题：3043. 最长公共前缀的长度

题目链接3043. 最长公共前缀的长度中等算法原理如果采用暴力解法遍历arr1的每个数再遍历arr2的每个数再去挨个用s.substring()去匹配那么时间复杂度会飙升到O(NML)的级别其中Lmax(arr1中数的最大长度arr2中数的最大长度)在此题的数据范围下必然会导致超时解法一字符串哈希表267ms击败5.55%时间复杂度O(L×(MN)),L是常数我们可以分别把arr1和arr2中各个数的前缀转成字符串存进哈希表中由于我们仅需找到所有arr1和arr2两两配对的最大前缀长度因此我们存哈希表的过程中无需存出现次数所以我们可以使用Set来存这样的话能够将复杂度从O(NML)降到O(NL)①分别处理arr1和arr2中的每个数通过s.substring()来获取该数字的前缀注意截取范围是[)因此写成s.substring(0,i1)将该前缀扔进Set②遍历哈希表1的每个字符串s判断哈希表2是否存在s如果存在s且长度更长就更新最大长度优化167ms击败36.11%时间复杂度O(L×(MN)),L是常数我们也可以只使用一个哈希表完成上述过程只处理arr1的所有数的前缀遍历arr2时直接判断更新解法二整数处理哈希表65ms击败75.00%时间复杂度O(L×(MN)),L是常数不断将元素x除以10直到0这个过程中的数即为x的前缀比如123→12→1→0代码实现时不需要计算长度而是直接取数值的最大值因为数值越大长度自然越长JAVA代码class Solution { //3043. 最长公共前缀的长度 //解法一字符串哈希表 public int longestCommonPrefix(int[] arr1, int[] arr2) { SetString hash1new HashSet(); SetString hash2new HashSet(); for(int x:arr1){ String sString.valueOf(x); for(int i0;is.length();i){ String pres.substring(0,i1);//截取范围在[0,i1) hash1.add(pre); } } for(int x:arr2){ String sString.valueOf(x); for(int i0;is.length();i){ String pres.substring(0,i1); hash2.add(pre); } } int ret0; for(String s:hash1) if(hash2.contains(s)s.length()ret) rets.length(); return ret; } }class Solution { //3043. 最长公共前缀的长度 //解法一优化字符串哈希表 public int longestCommonPrefix(int[] arr1, int[] arr2) { SetString hashnew HashSet(); for(int x:arr1){ String sString.valueOf(x); for(int i0;is.length();i) hash.add(s.substring(0,i1)); } int ret0; for(int x:arr2){ String sString.valueOf(x); for(int i0;is.length();i){ if(!hash.contains(s.substring(0,i1))) break; retMath.max(ret,i1); } } return ret; } }class Solution { //3043. 最长公共前缀的长度 //解法二整数处理哈希表 public int longestCommonPrefix(int[] arr1, int[] arr2) { SetInteger hashnew HashSet(); for(int x:arr1) for(;x0;x/10) hash.add(x); int mx0; for(int x:arr2){ while(x0!hash.contains(x)) x/10; mxMath.max(mx,x); } return mx0?Integer.toString(mx).length():0; } }