FilesExpand file tree

 master

/

LongestCommonPrefix14.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

83 lines (69 loc) · 2.08 KB

 master

/

LongestCommonPrefix14.java

Copy path

Top

File metadata and controls

• Code
• Blame

83 lines (69 loc) · 2.08 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

/**

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

*/

public class LongestCommonPrefix14 {

public String longestCommonPrefix(String[] strs) {

String lcp = "";

int S = strs.length;

if (S == 0) return lcp;

int L = strs[0].length();

int idx = 0;

for (int i = 1; i < S; i++) {

if (strs[i].length() < L) {

L = strs[i].length();

idx = i;

}

}

if (L == 0) return lcp;

int p = 1;

String possible = strs[idx];

while (p <= L) {

String sub = possible.substring(0, p);

boolean b = true;

for (int k = 0; k < S; k++) {

if (!strs[k].startsWith(sub)) {

b = false;

break;

}

}

if (!b) break;

lcp = sub;

p++;

}

return lcp;

}

/**

* https://discuss.leetcode.com/topic/6987/java-code-with-13-lines

*/

public String longestCommonPrefix2(String[] strs) {

if(strs == null || strs.length == 0) return "";

String pre = strs[0];

int i = 1;

while(i < strs.length){

while(strs[i].indexOf(pre) != 0)

pre = pre.substring(0,pre.length()-1);

i++;

}

return pre;

}

/**

* https://discuss.leetcode.com/topic/27913/sorted-the-array-java-solution-2-ms

*/

public String longestCommonPrefix3(String[] strs) {

StringBuilder result = new StringBuilder();

if (strs!= null && strs.length > 0){

Arrays.sort(strs);

char [] a = strs[0].toCharArray();

char [] b = strs[strs.length-1].toCharArray();

for (int i = 0; i < a.length; i ++){

if (b.length > i && b[i] == a[i]){

result.append(b[i]);

}

else {

return result.toString();

}

}

}

return result.toString();

}

}