题目描述

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。

示例 1：输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”

示例 2：输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。

题目分析

​ 我的思路 for循环取出每个字符串

​ 找出这些字符串中长度最小的一个 minLen，取出每个字符串的首字母 比较 。比较minLen次， 难点在于我不知道strs中有多少个字符串str，即使知道了也不能一次性把每个字符串str的首字母取出来比较。比如我有hashMap存储strs字符串数组，key—>是字符串str的下标strIndex，value—>char[]的，方便取出每个str的首字符

1
2
3
4
5
6
7
HashMap <Integer,char[]> map = new HashMap();
  int chhh =0;
  int strsLen = strs.length;
  	for(int j=0;j<strsLen;j++){
  		  char[] ch1 = map.get(j);
          chhh = Integer.valueOf(ch1[0]); 
  	}

​ 关键是这个chhh每次遍历一遍字符串数组strs就有strLen个，而且这么多个chhh名字相同而值不同。

​ 要是能让这些chhh带上标记（标记出这chhh是属于哪个字符串strs[j]的首字母），把每个str的chhh取出来，亦或。若每个chhh异或后=0，说明这个chhh是公共值。

​ 在把每个str的第二个元素取出来chhh2，异或每个chhh2若chhh2=0,说明是公共值。一直循环minLen次。chhhh[i] ^= chhhh[i+1];若循环每个str的首字母chhh后，chhh=0 说明chhh是公共前缀。代码太复杂不会写了。wuwuwu

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static String longestCommonPrefix(String[] strs) {
        int[] lenthS = new int[strs.length];
        HashMap<Integer, char[]> map = new HashMap<>();
        for(int i=0 ; i<strs.length; i++) {
            String s1 = strs[i];
            map.put(i,s1.toCharArray());
            lenthS[i]=s1.length();
        }
        int min = Integer.MAX_VALUE; // min是所有字符串中长度最小的一个
        for(int i=0; i<lenthS.length; i++) {
            if(lenthS[i] <min) {
                min=lenthS[i];
            }
        }
        int chhh;
        int strLen = 0;
        for(int j=0; j<strs.length; j++) { //取出每个字符串的
                char[] ch1 = map.get(j);
                chhh = Integer.valueOf(ch1[0]); //这是每个字符串的首字母
        }
		// 然后取出每个str的首字母 chhh
    	// 每个chhh异或，若chhh==0，chhh是公共值
    	// 循环minLen次就能找出最长的公共前缀

    }

参考答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public String longestCommonPrefix(String[] strs) {
       if(strs.length == 0) {
           return "";
       }
       String ans = strs[0];
       for(int i =1;i<strs.length;i++) {
           int j=0;
           for(;j<ans.length() && j < strs[i].length();j++) { 
               // j表示每个字符串中当前元素的下标
               // j要小于第一个字符串长度并且小于后面一个字符串的长度
               // j的最大值是---->当前字符串ans长度和下一个字符串strs[i]长度的较小哪个
               if(ans.charAt(j) != strs[i].charAt(j)){
                   // 若在j位 两个字符串的对应char值不一样
                   // 标记出出现差异的下标，退出内层循环
                   break;
               }
           }
           ans = ans.substring(0, j); // 截取第0个~第j个字符
           if(ans.equals("")) {
               return ans;
           }
       }
       return ans;
   }

参考代码的图解如下

  • avatar

对比总结

​ 我的想法很直接，是取出strs中每个字符串的首字母，在把这些首字母异或。若异或的结果等于0，就表明这是公共元素。首先这种做法不合理。因为不能一次性把每个字符串的首字符取出来一起比较。只能两个字符串的同一个下标索引的值比较。

​ 在看了参考代码后，我发现能用整体的思维比较【以每个字符串为单位,比较ans和strs[i]，用j为下标记录2个字符串间第一次有差异的位置，截取下标j之间的公共部分，让ans重新指向这个公共部分。而strs[i]也同样指向下一个字符串。这样淘汰的是整个长度较大字符串】。而不是以每个字符为单位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 发现参考答案的
 	for(int i =1;i<strs.length;i++) {
		for(int j=0;j<ans.length() && j < strs[i].length();j++) {}
	}
// 这段代码能代替我的
	int min = Integer.MAX_VALUE; // min是所有字符串中长度最小的一个
    for(int i=0; i<lenthS.length; i++) {
        if(lenthS[i] <min) {
            min=lenthS[i];
         }
   	}
 //同样是标记出所有字符串中长度最小的。只不过我一次性找出来，而参考答案是多次找出来。
 //就是分成多次操作才好用substring()方法截取公共部分，还有空间刷新ans和strs[i] !!!
 //我一开始没有想到用substring()而是以一个字符为单位，找出来而然后存入string[]中
 //这样不仅增加每个字符对比的难度还增加了数组拆分和组装的时间