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

题目链接：3043. 最长公共前缀的长度（中等）

算法原理：

如果采用暴力解法，遍历arr1的每个数，再遍历arr2的每个数，再去挨个用s.substring()去匹配，那么时间复杂度会飙升到O(NML)的级别，其中L=max(arr1中数的最大长度，arr2中数的最大长度)，在此题的数据范围下必然会导致超时

解法一：字符串+哈希表

267ms击败5.55%

时间复杂度O(L×(M+N)),L是常数

我们可以分别把arr1和arr2中各个数的前缀转成字符串存进哈希表中，由于我们仅需找到所有arr1和arr2两两配对的最大前缀长度，因此我们存哈希表的过程中无需存出现次数，所以我们可以使用Set来存，这样的话能够将复杂度从O(NML)降到O(NL)

①分别处理arr1和arr2中的每个数

通过s.substring()来获取该数字的前缀（注意截取范围是[)，因此写成s.substring(0,i+1)）

将该前缀扔进Set

②遍历哈希表1的每个字符串s，判断哈希表2是否存在s，如果存在s且长度更长，就更新最大长度

优化

167ms击败36.11%

时间复杂度O(L×(M+N)),L是常数

我们也可以只使用一个哈希表完成上述过程，只处理arr1的所有数的前缀，遍历arr2时直接判断更新

解法二：整数处理+哈希表

65ms击败75.00%

时间复杂度O(L×(M+N)),L是常数

不断将元素x除以10，直到0，这个过程中的数即为x的前缀

比如123→12→1→0

代码实现时，不需要计算长度，而是直接取数值的最大值，因为数值越大，长度自然越长

JAVA代码：

class Solution { //3043. 最长公共前缀的长度 //解法一：字符串+哈希表 public int longestCommonPrefix(int[] arr1, int[] arr2) { Set<String> hash1=new HashSet<>(); Set<String> hash2=new HashSet<>(); for(int x:arr1){ String s=String.valueOf(x); for(int i=0;i<s.length();i++){ String pre=s.substring(0,i+1);//截取范围在[0,i+1) hash1.add(pre); } } for(int x:arr2){ String s=String.valueOf(x); for(int i=0;i<s.length();i++){ String pre=s.substring(0,i+1); hash2.add(pre); } } int ret=0; for(String s:hash1) if(hash2.contains(s)&&s.length()>ret) ret=s.length(); return ret; } }

class Solution { //3043. 最长公共前缀的长度 //解法一优化：字符串+哈希表 public int longestCommonPrefix(int[] arr1, int[] arr2) { Set<String> hash=new HashSet<>(); for(int x:arr1){ String s=String.valueOf(x); for(int i=0;i<s.length();i++) hash.add(s.substring(0,i+1)); } int ret=0; for(int x:arr2){ String s=String.valueOf(x); for(int i=0;i<s.length();i++){ if(!hash.contains(s.substring(0,i+1))) break; ret=Math.max(ret,i+1); } } return ret; } }

class Solution { //3043. 最长公共前缀的长度 //解法二：整数处理+哈希表 public int longestCommonPrefix(int[] arr1, int[] arr2) { Set<Integer> hash=new HashSet<>(); for(int x:arr1) for(;x>0;x/=10) hash.add(x); int mx=0; for(int x:arr2){ while(x>0&&!hash.contains(x)) x/=10; mx=Math.max(mx,x); } return mx>0?Integer.toString(mx).length():0; } }