Longest Common Prefix - String - Easy - LeetCode

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: ""

Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.String
{
 public class LongestCommonPrefixSoln
 {
 public string LongestCommonPrefix(string[] strs)
 {
 if(strs.Length == 0)
 {
 return "";
 }

 if(strs.Length == 1)
 {
 return strs[0];
 }

 int minLength = Int16.MaxValue;
 for (int i = 0; i < strs.Length; i++)
 {
 if(strs[i].Length < minLength)
 {
 minLength = strs[i].Length;
 }
 }

 if(minLength == Int16.MaxValue)
 {
 minLength = 0;
 }

 for(int i = 0; i < minLength; i++)
 {
 char ch = strs[0][i];
 for(int j = 1; j < strs.Length; j++)
 {
 if(ch != strs[j][i])
 {
 return strs[0].Substring(0, i);
 }
 }
 }

 return strs[0].Substring(0,minLength);
 }
 }
}

Time Complexity: O(n*m) where n is the number of strings and m is the shortest string length.

Space Complexity: O(1)

Unit Tests:

using LeetCode.AskGif.Easy.String;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;

namespace CodingUnitTest.Easy.String
{
 [TestClass]
 public class LongestCommonPrefixSolnTests
 {
 [TestMethod]
 public void LongestCommonPrefixSoln_First()
 {
 var input = new string[] { "flower", "flow", "flight" };
 var output = "fl";
 var res = new LongestCommonPrefixSoln().LongestCommonPrefix(input);

 Assert.AreEqual(res, output);
 }

 [TestMethod]
 public void LongestCommonPrefixSoln_Second()
 {
 var input = new string[]{"dog", "racecar", "car"};
 var output = "";
 var res = new LongestCommonPrefixSoln().LongestCommonPrefix(input);

 Assert.AreEqual(res, output);
 }

 [TestMethod]
 public void LongestCommonPrefixSoln_Third()
 {
 var input = new string[] { "c", "c" };
 var output = "c";
 var res = new LongestCommonPrefixSoln().LongestCommonPrefix(input);

 Assert.AreEqual(res, output);
 }
 }
}