Longest Common Prefix – Leetcode #14

Problem Statement

This problem is from Leetcode – Longest Common Prefix. The problem statement is as below:

Given an array of strings, return the longest common prefix. If none, return an empty string.

Solution

Lets see the brute force approach:

1. Store the first string from the input array in a variable – firstStr.
2. Now in a for loop read each character from firstStr and store in another char variable.
3. In another nested for loop we’ll iterate through the remaining strings in the input array and check if this char is present at the same index as firstStr.
4. If present then we’ll add this character in our prefix variable to be returned as answer.
5. Since we are using two nested for loops here, the time complexity of this approach in O(n²)

Lets see the code sample below:

	 
        /*
	     *   Input String Array: {"flower","floor","flight"}
        */
	 public String longestCommonPrefix(String[] strs) {
		 
		 String prefix = "";
		 boolean isPresent = true;
		 
		 // store the first string from the input array in a string variable
		 String firstStr = strs[0];
		 
		 
		 /*
		  * In a for loop read character from firstStr 
		  */
		 for(int i=0; i<firstStr.length(); i++) {
			 
			 // store the char at index i in a variable chr
			 char chr = firstStr.charAt(i);
			 
			 /*
			  * now iterate the input array from the second string
			  */
			 for(int j=1; j<strs.length; j++) {
				 
				 String curStr = strs[j];
				 if(curStr.length() > i) {
					 
					 /*
					  * here we check if the character chr is present at the same
					  * index position in this string
					  */
					 if(chr == curStr.charAt(i) ) {
						 
						 // if yes then store in a boolean variable
						 isPresent = true;
						 
					 } // end if
					 else {
						
						 return prefix;
					 }
					 
				 } // end if
				 else {
					 
					 return prefix;
				 }
				 
			 } // end for
			 
			 if(isPresent) {
				 
				 // add the character chr in the prefix to be returned
				 prefix = prefix + chr;
			 }  // end if
			 
		 }  // end for
		 
		 return prefix;
		 
	 }  // end function

This code returns the following output:

Longest common prefix: fl

You can check out the code from Github here – Longest Common Prefix – First Approach

PERFORMANCE ANALYSIS

RUNTIME	8 ms | Beats 8.86 %
MEMORY	42.33 MB | Beats 7.91 %
TIME COMPLEXITY	O ( N2 )