Counting Sort Algorithm
Counting sort runs on relatively smaller set of input. Counting sort calculates…
September 13, 2019
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Note: All given inputs are in lowercase letters a-z.
Lets look at a simple solution, where we will look in entire strings for the match.
public String longestCommonPrefix(String[] strs) {
int strsLen = strs.length;
if (strsLen == 0) {
return "";
}
int l = strs[0].length();
StringBuffer sb = new StringBuffer();
for (int i=0; i<l; i++) {
char ch = strs[0].charAt(i);
boolean matched = true;
for (int j=1; j<strsLen; j++) {
if (i >= strs[j].length() || ch != strs[j].charAt(i)) {
matched = false;
break;
}
}
if (!matched) {
break;
}
sb.append(ch);
}
return sb.toString();
}
We can use divide and conquer, and then merge the result. Since, common of two strings will be eligible to match from other strings.
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
return helper(strs, 0, strs.length-1);
}
private String findRes(String l, String r) {
int len = Math.min(l.length(), r.length());
int i=0;
for (; i<len; i++) {
if (l.charAt(i) != r.charAt(i)) {
break;
}
}
return l.substring(0, i);
}
private String helper(String[] strs, int l, int r) {
if (l == r) return strs[l];
int m = (l+r)/2;
String left = helper(strs, l, m);
String right = helper(strs, m+1, r);
return findRes(left, right);
}
Counting sort runs on relatively smaller set of input. Counting sort calculates…
Problem Statement Given a string s, find the longest palindromic substring in s…
** Inversion There is an array(a) and two indexes i and j. Inversion is the…
Problem Statement Roman numerals are represented by seven different symbols: I…
This algorithm is very useful for large input. And, is quite efficient one. It…
Problem Statement Given n non-negative integers a1, a2, …, an , where each…
Introduction In this post we will see following: How to schedule a job on cron…
Introduction There are some cases, where I need another git repository while…
Introduction In this post, we will see how to fetch multiple credentials and…
Introduction I have an automation script, that I want to run on different…
Introduction I had to write a CICD system for one of our project. I had to…
Introduction Java log4j has many ways to initialize and append the desired…