C#•7mo ago

Fighting with the longest common prefix puzzle

Link to the puzzle description https://leetcode.com/problems/longest-common-prefix/submissions as always I had a small hiccups . Here's my WIP code

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        string res = "";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strs.Length; i++)
        {
            string commonChars = string.Concat(strs
                .Select(strs=>strs.AsEnumerable())
                .Aggregate((s,a)=>s.Intersect(a))
                .OrderBy(c=>c)
                );
            
            res = commonChars;
        }
        

        return res;
    }
}

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        string res = "";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strs.Length; i++)
        {
            string commonChars = string.Concat(strs
                .Select(strs=>strs.AsEnumerable())
                .Aggregate((s,a)=>s.Intersect(a))
                .OrderBy(c=>c)
                );
            
            res = commonChars;
        }
        

        return res;
    }
}

` And this code is stuck with the following test case as per screenshot. It's fine with all the other test cases. I assume Linq has some functions to compare the length of the common chars, but I am not versed with this technology. I assume Linq has a function to skip non-common chars sitting between the common chars (like in the screenshot) Can anyone point me in the right direction?

22 Replies

ACiDCA7•7mo ago

why do you want to do this with linq? i guess there might be a way solve it with linq, but seems inefficient the simplest solution are often the best ;)

morry329#OP•7mo ago

i tried the iterative approach first but failed my code could not pick up the first common char in the (potential) common prefix correctly. it was ok with two strings in one string array. it does not work anymore with three or more strings in one string array. i googled how to fix that then the linq approach came up

ACiDCA7•7mo ago

wanna share how you tried it? maybe we find the issue ;)

morry329#OP•7mo ago

Sure 😉 Here's how I tried it I felt a bit stuck while trying to verify char at idx 0 is the same for all entries. My code can verify that if it's just two entries. If it's more than three entries the code does not verify the common char for all entries.

StringBuilder sb = new StringBuilder();
for(int i = 0; i < strs.Length; i++){
   string element1 = strs[i];
   string element2 = strs[i+1];
   
   //1st check - trying to check the common char at index 0 (like "fl" in the test case)
   if(element1[0] == element2[0]){
   Console.WriteLine("common char found");
   sb.Append(element1[0]);
   //continue to check the other chars at index 1+ only after passing the 1st check 
   for(int j = 1; j < strs.Length; j++){
   //tbc
   }   
   }

StringBuilder sb = new StringBuilder();
for(int i = 0; i < strs.Length; i++){
   string element1 = strs[i];
   string element2 = strs[i+1];
   
   //1st check - trying to check the common char at index 0 (like "fl" in the test case)
   if(element1[0] == element2[0]){
   Console.WriteLine("common char found");
   sb.Append(element1[0]);
   //continue to check the other chars at index 1+ only after passing the 1st check 
   for(int j = 1; j < strs.Length; j++){
   //tbc
   }   
   }

ACiDCA7•7mo ago

hmm how do i explain this without spoiling the solution..xD you get via the parameter a array of strings to compare eg the first string at first index with second string and first index you can do it like this

strs[0][0] == strs[1][0]

strs[0][0] == strs[1][0]

MODiX•7mo ago

ACiDCA7

REPL Result: Success

var strs = new string[]{"abc","bcd","cde"};
Console.WriteLine(strs[1][1]); //prints "c" of the second string

var strs = new string[]{"abc","bcd","cde"};
Console.WriteLine(strs[1][1]); //prints "c" of the second string

Console Output

Compile: 320.703ms | Execution: 26.250ms | React with ❌ to remove this embed.

ACiDCA7•7mo ago

i think this is what you were missing to complete the challenge ;)

morry329#OP•7mo ago

Ohh I see! I have not noticed that comparison 🙂 I will try it out right away

ACiDCA7•7mo ago

i believe in you ;)

morry329#OP•7mo ago

Hmm, so on my IDE my code passed all potential test cases I could found. But the leetcode flags IndexOutOfRangeException. I don't know why This is the code in question

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        string res = "";
        StringBuilder sb = new StringBuilder();
        
        if(strs.Length==1){
            sb.Append(strs[0]);
        }
        for (int i = 0; i < strs.Length-1; i++)
        {
            
            if (strs[0][0] == strs[1][0] && strs[0][0] == strs[i][0])
            {
                Console.WriteLine($"passed the first check");
                sb.Append(strs[0][0]); //or append strs[i][0]
            }
            for (int j = 1; j < strs.Length-1; j++)
            {
                if (strs[0][1] == strs[j][j])
                {
                    Console.WriteLine($"common prefix getting longer");
                    sb.Append(strs[j][j]);
                }
                
            }
        }    
        

        return new string (sb.ToString().ToCharArray().Distinct().ToArray());
    }
}

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        string res = "";
        StringBuilder sb = new StringBuilder();
        
        if(strs.Length==1){
            sb.Append(strs[0]);
        }
        for (int i = 0; i < strs.Length-1; i++)
        {
            
            if (strs[0][0] == strs[1][0] && strs[0][0] == strs[i][0])
            {
                Console.WriteLine($"passed the first check");
                sb.Append(strs[0][0]); //or append strs[i][0]
            }
            for (int j = 1; j < strs.Length-1; j++)
            {
                if (strs[0][1] == strs[j][j])
                {
                    Console.WriteLine($"common prefix getting longer");
                    sb.Append(strs[j][j]);
                }
                
            }
        }    
        

        return new string (sb.ToString().ToCharArray().Distinct().ToArray());
    }
}

` I think I need to break the loops

ACiDCA7•7mo ago

strs[j][j] this is wrong: j is the amount of strings provided. you are trying here to to access in the j string the j character you can remove this

if (strs[0][0] == strs[1][0] && strs[0][0] == strs[i][0])
            {
                Console.WriteLine($"passed the first check");
                sb.Append(strs[0][0]); //or append strs[i][0]
            }

if (strs[0][0] == strs[1][0] && strs[0][0] == strs[i][0])
            {
                Console.WriteLine($"passed the first check");
                sb.Append(strs[0][0]); //or append strs[i][0]
            }

why arent you using i?

if (strs[0][1] == strs[j][j])
                {
                    Console.WriteLine($"common prefix getting longer");
                    sb.Append(strs[j][j]);
                }

if (strs[0][1] == strs[j][j])
                {
                    Console.WriteLine($"common prefix getting longer");
                    sb.Append(strs[j][j]);
                }

you are using the same loop twice but i guess u want to instead loop for the amount of chars right?

 for (int j = 1; j < strs.Length-1; j++)

 for (int j = 1; j < strs.Length-1; j++)

you can do this eg by

 for (int j = 1; j < strs[0].Length-1; j++)

 for (int j = 1; j < strs[0].Length-1; j++)

morry329#OP•7mo ago

Ahhh I see! I did not realised I used the same loop twice 🤦‍♀️ The reason being for using i is that I read a potential workflow (not a complete solution, just a text instruction) to solve this puzzle. The instruction says as follows: loop over the array, check the first char of every string element in the string array and see if they are common chars, increment the index by 1, loop over the array again, check any other n-th char of every string element to see if they are common chars. I think I misunderstood this part: loop over the array again, check any other n-th char of every string element to see if they are common chars. Whilst my code needed to loop over the array again, I somehow thought I need to create a new loop to do that. My thought process was as follows: ok I found the common char on the first indexes of every single string element (with your help). So that is why I created the second (aka the same old as the first one) loop without using the index i. Aw, I am not good at this logical thinking to write a code. Often I don't even understand what I wanted to do with any specific line of my code

ACiDCA7•7mo ago

so did you find a solution? or should i go more into depth how to loop over every char in every string?

morry329#OP•7mo ago

Yes, please go more into depth how to do that. This is my incomplete code as of this morning

public string LongestCommonPrefix(string[] strs) {
        string res = "";
        StringBuilder sb = new StringBuilder();
        if (string.IsNullOrWhiteSpace(strs[0]))
        {
            Console.WriteLine("null null");
            return "";
        }
        if(strs.Length==1){
            sb.Append(strs[0]);
        }
        for (int i = 1; i < strs.Length; i++)
        {
            
            if (strs[0][0] == strs[i][0])
            {
                Console.WriteLine($"passed the first check");
                sb.Append(strs[i][0]); //or append strs[i][0]
                for (int j = 0; j < strs[0].Length; j++)
                {
                    //i++;
                    if (strs[0][j] == strs[i][j]) //bei cir cis strs[i][0] == strs[i][j] geht. 
                    {
                        Console.WriteLine($"common prefix getting longer");
                        sb.Append(strs[i][j]);
                    }
                
                }
            }
            
        }    
        

        return new string (sb.ToString().ToCharArray().Distinct().ToArray());
    }

public string LongestCommonPrefix(string[] strs) {
        string res = "";
        StringBuilder sb = new StringBuilder();
        if (string.IsNullOrWhiteSpace(strs[0]))
        {
            Console.WriteLine("null null");
            return "";
        }
        if(strs.Length==1){
            sb.Append(strs[0]);
        }
        for (int i = 1; i < strs.Length; i++)
        {
            
            if (strs[0][0] == strs[i][0])
            {
                Console.WriteLine($"passed the first check");
                sb.Append(strs[i][0]); //or append strs[i][0]
                for (int j = 0; j < strs[0].Length; j++)
                {
                    //i++;
                    if (strs[0][j] == strs[i][j]) //bei cir cis strs[i][0] == strs[i][j] geht. 
                    {
                        Console.WriteLine($"common prefix getting longer");
                        sb.Append(strs[i][j]);
                    }
                
                }
            }
            
        }    
        

        return new string (sb.ToString().ToCharArray().Distinct().ToArray());
    }

And this code fails at the testcase where all the elements are the same char combination/word as per attached screenshot So I appreciate any advice as to how to loop over with it

ACiDCA7•7mo ago

hopefully my scribbling is readable..xD x is the word y is the letter in that word the logic of you latest snippet is doing this: you go through each word skipping the first ( btw good catch;) ) comparing if the first letter is matching with the first word if its the case you loop through each char in that word an compare it with the first word. its possible to do it this way but i would propose a different way instead of checking whole strings with each other go the other route and only compare only a letter at a time but for every word btw do you know how to use the debugger?

for (int i = 0; i < strs[0].Length; i++)
{
  for (int j = 1; j < strs.Length; j++)
  {
    // an if here that i dont want to spoil
  }
}

for (int i = 0; i < strs[0].Length; i++)
{
  for (int j = 1; j < strs.Length; j++)
  {
    // an if here that i dont want to spoil
  }
}

hopefully this isnt already a too big spoiler...

morry329#OP•7mo ago

Thank you for the scribbling and the matrix with the texts 🙏 It is a massive help hmm, I hope I understood you correctly. so if i would like to compare the letter at the 0 index, I would compare strs[0][0] with strs[0][1] and strs[0][2] (it continues until it reaches strs[0][n] with n being the length of strs (the array)) - am I thinking it over correctly? Yes and no. I feel like I still don't understand what my debugger shows to me. Even so debugging helped me to come up with the catches for the edge cases (like returning the entry if the length of the array is 1, or returning the empty string if the array entries are all null strings etc)

ACiDCA7•7mo ago

so if i would like to compare the letter at the 0 index, I would compare strs[0][0] with strs[0][1] and strs[0][2] (it continues until it reaches strs[0][n] with n being the length of strs (the array)) - am I thinking it over correctly?

no if you want to compare the first letter of the first word with the first letter in second word its strs[0][0] and strs[1][0] the third word would be strs[2][0] and so on basicly strs[word][letter] so if you want to compare the second letter then its strs[0][1] strs[1][1] strs[2][1] and so on i had hoped on the right side the text should drive that point home..xD

morry329#OP•7mo ago

yeah, I got that it's strs[word][letter] i'm like either I have trouble translating this into code or i have trouble understanding the comparison of letters so i will code the if block on my own, but this is the only if block I can think of

for (int i = 0; i < strs[0].Length; i++)
{
  for (int j = 1; j < strs.Length; j++)
  {
    if(strs[i][j] == strs[i+1][j+1]){
        sb.Append(strs[i][j]); 
    }
  }
}

for (int i = 0; i < strs[0].Length; i++)
{
  for (int j = 1; j < strs.Length; j++)
  {
    if(strs[i][j] == strs[i+1][j+1]){
        sb.Append(strs[i][j]); 
    }
  }
}

` I know this is not the right if block. it gave me IndexOutOfRangeException so many times

ACiDCA7•7mo ago

with that snippet there are 2 scenarios where you get IndexOutOfRangeException 1. if a word is shorter than the first word you will try to access a letter that does not exists 2. when you reach the end of the list you get the error because when doing i+1 you try to access a word that does not exist so you have to have beside comparison a stop condition that doesnt continue where it shouldnt if you were the computer step by step how would you try to solve this?

morry329#OP•7mo ago

For the 2.: hm I would check if the word (on the i+1th) next to the current word (on the ith) is null. Right now I have the catch that checks if the current word is null. So I would add the extra catch for the current.next word is null For the 1. Oh that is a tricky question for me I just drew this to think about the 1st scenario (I hope you can open the attachment to see the pic) In this case the code will trigger IndexOutOfException if it tries accessing the 4th char of "flow" as it does not exist. So I am just wondering if I could add extra check to the code like if strs[fixed][j+1] is null, break the loop or something like that

ACiDCA7•7mo ago

yes you will need a condition to stop further looping btw you dont need any +1s to solve this puzzle

morry329#OP•7mo ago

Alright - I actually peeked into some solutions. None of them used any +1s to solve the puzzle. They have doubled loops like we tried implementing and inside the doubled loop they have the if block too. But the condition within the if is like : strs[stringIndex] <= strs.Length && compare != strs[i][j] I have a tendency to rely on 1+s instead of making use of the index combinations like this one. I have been visiting this site and practicing it for about 1,5 years but I feel like my problem solving skills could have been improved more I am not sure if I try not to peek into a solution until I am so stuck (which happens to me so often) that I cannot think it straight. Or it is also one of the options for me to quickly take a grande at the solution after I fight for about a day or two Unfortunately I cannot invest many hours in Leetcode (my hobby) as I have a lot to do every day 😦

Gaming

Programming

Fighting with the longest common prefix puzzle