binary search approach - C# version


  • 0
    R
    public class Solution {
        public string LongestCommonPrefix(string[] strs) {
            return CommonPrefix(strs, 0, strs.Length-1);
        }
        string CommonPrefix(string[] arr, int low, int high)
    {
    	if(low==high)
    	return arr[low];
    
    	if (high > low)
    	{
    		int mid = low + (high-low)/2;
    		string str1 = CommonPrefix(arr,low, mid);
    		string str2 = CommonPrefix(arr,mid+1, high);
    		return CommonPrefixUtil(str1, str2);
    	}
    	return string.Empty;
    }
    
    string CommonPrefixUtil(string str1, string str2)
    {
    	int m = str1.Length;
    	int n = str2.Length;
    	StringBuilder sb = new StringBuilder();
    	for (int i = 0, j=0; i < m && j < n; i++, j++)
    	{
    		if(str1[i] != str2[j])
    		break;
    		else sb.Append(str1[i]);
    	}
    	return sb.ToString();
    }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.