Longest Common Prefix

Longest Common Prefix

Given k strings, find the longest common prefix (LCP).

Example

For strings `"ABCD"`, `"ABEF"` and `"ACEF"`, the LCP is `"A"`

For strings `"ABCDEFG"`, `"ABCEFG"` and `"ABCEFA"`, the LCP is `"ABC"`

```public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String lcp = strs[0];
for (int i = 1; i < strs.length; i++) {
lcp = getLCP(lcp, strs[i]);
}
return lcp;
}

public String getLCP(String s1, String s2) {
StringBuilder sb = new StringBuilder();
int n = Math.min(s1.length(), s2. length());
for (int i = 0; i < n; i++) {
if (s1.charAt(i) == s2.charAt(i)) {
sb.append(s1.charAt(i));
} else {
break;
}
}
return sb.toString();
}```

Share

Palindrome Partitioning

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

given s = `"aab"`,
Return

```  [
["aa","b"],
["a","a","b"]
]```

Solution: DFS, Subsets变种题 考虑每个间隙是partition还是不partition

```public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
partitionHelper(s, new ArrayList<String>(), result);
return result;
}

public void partitionHelper(String s, ArrayList<String> curr, List<List<String>> result) {
if (s.length() == 0) {
return;
}
for (int i = 0; i < s.length(); i++) {
String currString = s.substring(0, i + 1);
if (isPalindrome(currString)) {
partitionHelper(s.substring(i + 1), curr, result);
curr.remove(curr.size() - 1); //important
}
}
}

public boolean isPalindrome(String s) {
int start = 0;
int end = s.length() - 1;
while (start <= end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}```

Leetcode: Valid Number

Validate if a given string is numeric.

Some examples:
`"0"` => `true`
`" 0.1 "` => `true`
`"abc"` => `false`
`"1 a"` => `false`
`"2e10"` => `true`

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

```public boolean isNumber(String s) {
// Start typing your Java solution below
// DO NOT write main() function
if(s==null||s.length()==0){
return false;
}
//continuous zeros from beginning since begin is true
int cont = 0;
boolean hasDot = false;
boolean begin = false;
boolean end = false;
boolean hasSign = false;
boolean hasE = false;

for(int i=0;i<s.length();i++){
char c = s.charAt(i);

if(c=='+'||c=='-'){
if(hasSign||begin){
return false;
}else{
hasSign = true;
}
continue;
}

if(c=='e'){
if(hasE||!begin){
return false;
}else{
return isInteger(s.substring(i+1));
//return true;
}
}

if(c=='.'){
if(hasDot||end){
return false;
}else{
hasDot = true;
}
continue;
}

if(c==' '){
if((begin ||hasSign) && !end){
end=true;
}
continue;
}

if(!(isDigit(s,i))){
return false;
}else{
if(end){
return false;
}else{
if(!begin){
begin=true;
}
}
}

}

if(!begin){
return false;
}
return true;

}
public boolean isInteger(String s){
if(s==null||s.length()==0){
return false;
}
if(s.length()==1 && isDigit(s,0)){
return true;
}
char c = s.charAt(0);
if(c=='0'){
return ifAllSpace(s.substring(1));
}
int zeors = 0;
for(int i=0;i<s.length();i++){
if(i==0){
if(c=='+'||c=='-'){
return isIntegerWithoutSign(s.substring(i+1));
}else
if(!isDigit(s,i)){
return false;
}
}else
if(!isDigit(s,i)){
if(c==' '){
return ifAllSpace(s.substring(i+1));
}else{
return false;
}
}
}
return true;
}

public boolean ifAllSpace(String s){
for(int i=0;i<s.length();i++){
if(s.charAt(i)!=' '){
return false;
}
}
return true;
}

public boolean isIntegerWithoutSign(String s){
if(s==null||s.length()==0){
return false;
}
if(s.length()==1 && isDigit(s,0)){
return true;
}
char c = s.charAt(0);
if(c=='0'){
return false;
}
for(int i=0;i<s.length();i++){
if(!isDigit(s,i)){
if(c==' '){
return ifAllSpace(s.substring(i));
}else{
return false;
}
}
}
return true;
}

public boolean isDigit(String s,int index){
char c = s.charAt(index);
if(c<(int)'0' || c>(int)'9'){
return false;
}
return true;
}```

Leetcode: Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

```public String strStr(String haystack, String needle) {
// Start typing your Java solution below
// DO NOT write main() function
if(needle==null){
return haystack;
}

int start = 0;
int index1 = 0;
int index2 = 0;
while(index1<haystack.length() && index2<needle.length()){
if(haystack.charAt(index1)==needle.charAt(index2)){
index1++;
index2++;
}else{
start++;
index1=start;
index2=0;

}
}
if(index2==needle.length() && index1-start==needle.length()){
return haystack.substring(start);
}else{
return null;
}
}```