Radix Sort Algorithm
A number consists of digits. Example: 843. Its a 3-digit number. Radix sort…
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.
Now, iterate to this length.
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);
}
A number consists of digits. Example: 843. Its a 3-digit number. Radix sort…
Problem Statement Given n non-negative integers a1, a2, …, an , where each…
Counting sort runs on relatively smaller set of input. Counting sort calculates…
This is another very useful sorting algorithm based on Heap data structure. Read…
Problem Statement Given a linked list, swap every two adjacent nodes and return…
A Binary tree is a data structure which has two children nodes attached to it…
Problem Statement You are given a string text of words that are placed among…
Problem Statement You are given a rows x cols matrix grid. Initially, you are…
Problem Statement Given a string s, return the maximum number of unique…
Problem The Leetcode file system keeps a log each time some user performs a…
Problem Statement Replace all spaces in a string with ‘%20’ (three characters…
Problem Implement an algorithm to determine if a string has all the characters…