Binary Tree - Level Order Traversal
Problem Statement Given a Binary tree, print out nodes in level order traversal…
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);
}
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement You are given an n x n 2D matrix representing an image, rotate…
Problem The Leetcode file system keeps a log each time some user performs a…
Problem Statement Given an array nums of n integers and an integer target, find…
Problem Statement Say you have an array prices for which the ith element is the…
A number consists of digits. Example: 843. Its a 3-digit number. Radix sort…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement Given an array nums of n integers and an integer target, are…