Leetcode Solutions #1

1. Longest Common Prefix

The Problem

Let's read the description first:

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

Question is not that hard to understand from the description in this question you have to check for the longest common prefix among a given array of string. If there is no common prefix just simply return "".

Refer to the examples given below:

Approach

Basic approach here should be that when we have to find something common among a set of items, we compare the first item with others. Similarly here we will use the same kind of approach in following steps:

1. Set the first string as the prefix.
2. Compare the first string with all other given strings.
3. Keep reducing the length of string to find the common prefix.

Solution

In the solution,

1. Set the first string of the vector strs as the prefix.
2. Iterate through the remaining string using for loop.
3. While loop checks if the current string starts with the current prefix. If not the loop will run.
4. If prefix is not found prefix.substr(0, prefix.length()-1) this will trim one character from the end and creates a new string from starting to second last character of prefix.
5. If prefix not found even after trimming return "".
6. Else return prefix.

2. Sort Characters By Frequency

The Problem

Let's Read the description first:

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

The description is pretty basic and understandable about what we need to achieve in this question.

Refer to the examples given below:

Approach

This question is pretty basic approach wise, we can do this in the following steps:

1. Create an unordered map to record the frequencies of characters.
2. Make character frequency pair of every character appearing in the string.
3. Sort the string and return the result.

Solution

In the solution,

1. I have declared an unordered map frq that will store characters as key and their frequencies as values.
2. Use for loop to iterate over each character in the given string and record their frequencies.
3. A vector of pairs freqpair is created using the elements from the frq map. Each element in the freqpair vector contains a character and its frequency as a pair. The map is transformed into a vector to allow sorting based on the frequency.
4. I have used basic bubble sort for the sorting purpose.
5. Declare a for loop that goes through the sorted freqpair vector. For each pair p, it appends the character to the result string, repeated p.second times.
6. Return result.

String to Integer (atoi)

The Problem

Let's Read the description first:

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

The algorithm for myAtoi(string s) is as follows:

1. Whitespace: Ignore any leading whitespace (" ").

2. Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity is neither present.

3. Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0.

4. Rounding: If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.

Return the integer as the final result.

In my opinion, this question just looks scary but is very easy to deal with just ignore the description and focus on the part that you have to convert a string to integer with some conditions like:

1. There should not be any leading whitespaces.
2. Check for the signs that the character is '-' or '+'.
3. Check for the non digit characters, if you encounter non digit character you have to stop reading.
4. Handle the integer overflow.

Refer to the examples below:

Approach

There is nothing special going to be with the approach you just have to look out for the conditions mentioned in the description and convert the string to int. Let's go to the solution.

Solution

In the solution,

1. Declare and initialize three variable index(to traverse string s), num(to store the resultant integer), negative(to check whether number is negative or not).
2. Use while loop to check for any leading whitespace, the function isspace checks if the current character is whitespace. Loop will continue until a non whitespace character is found.
3. Now, we will check for the sign if the current character is '-' or '+' sign. If character is '-' sign the negative is set to be true and index is incremented to move past the sign.
4. Here, this while loop continues until it encounters a non-digit character. int digit = s[index] - '0' converts the character at a particular index from its ASCII value to numeric value.
5. This if statement checks for overflow. If adding the next digit would cause num to exceed the 32-bit signed integer limit (INT_MAX), the function returns the appropriate value.
6. If there is no overflow, current digit is added to num. The number is updated by multiplying num by 10 and adding the value of the current digit. The index is then incremented to move to the next character.
7. After processing all digits if negative is true, num is made negative by multiplying by -1.
8. Now return num.

I hope the solutions I have provided are understandable and explanations are easy to understand.

Thank You

You can connect with me on linkedin