LeetCode之Longest Common Prefix

1、题目

Write a function to find the longest common prefix string amongst an array of strings

2、代码实现

package leetcode.chenyu.test;

public class LongestCommonPrefix {
public static void main(String[] args)  {
String [] ss = {"12345", "3234", "234"};
String [] ss1 = {"flower", "flow", "flight"};
String [] ss2 = {"ca", "a"};
String [] ss3 = {"a", "a"};
String [] ss4 = {"aa","ab"};
String [] ss5 = {"abca","aba","aaab"};
String result =longestCommonPrefix(ss5);
System.out.printf("result1111:" + result);

}
public static boolean isNull(String s) {
if(s == null || s.length() == 0) {
return true;
}
return false;
}
public  static String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length ==0) {
return "";
}
int length = strs.length;
if (length == 1) {
return strs[0];
}
int minLength = Integer.MAX_VALUE;
int index = 0;
for (int i = 0; i < strs.length; ++i) {
 if (isNull(strs[i])) {
 return "";
 }
 if (minLength > strs[i].length()) {
 minLength = strs[i].length();
 index = i;
 }
}
String result = "";
for (int i = 1; i <= minLength; ++i) {
 int count = 0;
 for (int j = i; j <= minLength; ++j) {
  String s =  strs[index].substring(count++, j);
  System.out.print("s:" + s + "\t");
  int flag = 0;
  for (int k = 0; k < length; k++) {
  if (k != index) {
  if (!strs[k].contains(s)) {
  break;
  } else {
 flag++;
 System.out.print("flag:" + flag + "\t");
 if (flag == length - 1) {
 if (result.length() < s.length()) {
  int num = 0;
  for (int h = 0; h < length; h++) {
   if (!strs[h].startsWith(s)) {
    break;
   } else {
   num++;
   }
  }
  if (num == length)
  result = s;
 }
 System.out.println("result:" + result + "\t");
 break;
 }
   }
   }
  }
 }
}
return result;
}
}

特么一开始看错题目，虽然结果验证没有出问题，但是超时了，日了狗

下面的代码是求 字符串数组种最大的公共子串

package leetcode.chenyu.test;

public class LongestCommonPrefix {
public static void main(String[] args)  {
String [] ss = {"12345", "3234", "234"};
String [] ss1 = {"flower", "flow", "flight"};
String [] ss2 = {"ca", "a"};
String [] ss3 = {"a", "a"};
String [] ss4 = {"aa","ab"};
String [] ss5 = {"abca","aba","aaab"};
String result =longestCommonPrefix(ss5);
System.out.printf("result1111:" + result);

}
public static boolean isNull(String s) {
if(s == null || s.length() == 0) {
return true;
}
return false;
}
public  static String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length ==0) {
return "";
}
int length = strs.length;
if (length == 1) {
return strs[0];
}
int minLength = Integer.MAX_VALUE;
int index = 0;
for (int i = 0; i < strs.length; ++i) {
 if (isNull(strs[i])) {
 return "";
 }
 if (minLength > strs[i].length()) {
 minLength = strs[i].length();
 index = i;
 }
}
String result = "";
for (int i = 1; i <= minLength; ++i) {
 int count = 0;
 for (int j = i; j <= minLength; ++j) {
  String s =  strs[index].substring(count++, j);
  System.out.print("s:" + s + "\t");
  int flag = 0;
  for (int k = 0; k < length; k++) {
  if (k != index) {
  if (!strs[k].contains(s)) {
  break;
  } else {
 flag++;
 System.out.print("flag:" + flag + "\t");
 if (flag == length - 1) {
 if (result.length() < s.length()) {
  result = s;
 }
 System.out.println("result:" + result + "\t");
 break;
 }
   }
   }
  }
 }
}
return result;
}
}

最后修改后可以通过LeetCode的代码

public class Solution {
    public static boolean isNull(String s) {
if(s == null || s.length() == 0) {
return true;
}
return false;
}
public  static String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length ==0) {
return "";
}
int length = strs.length;
if (length == 1) {
return strs[0];
}
int minLength = Integer.MAX_VALUE;
int index = 0;
for (int i = 0; i < strs.length; ++i) {
 if (isNull(strs[i])) {
 return "";
 }
 if (minLength > strs[i].length()) {
 minLength = strs[i].length();
 index = i;
 }
}
String result = "";
for (int i = 1; i <= minLength; ++i) {
String s =  strs[index].substring(0, i);
int flag = 0;
for (int k = 0; k < length; k++) {
if (k != index) {
if (!strs[k].contains(s) || !strs[k].startsWith(s)) {
break;
} else {
flag++;
    if (flag == length - 1) {
if (result.length() < s.length()) {
result = s;
}
    break;
   }
     }
     }
     }
}
return result;
}
}