Skip to content

Commit d557870

Browse files
author
Gabriel Albuquerque da Rosa
committed
feat: 125. Valid Palindrome solution and corresponding tests
1 parent 893f013 commit d557870

3 files changed

Lines changed: 88 additions & 0 deletions

File tree

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@ This repository contains solutions to various LeetCode problems implemented in C
1313
| 42 | [Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/) | Hard | [Code](https://github.com/gabaoalb/LeetCodeCSharp/blob/main/Solutions/Problems/TrappingRainWater.cs) |
1414
| 49 | [Group Anagrams](https://leetcode.com/problems/group-anagrams/) | Medium | [Code](https://github.com/gabaoalb/LeetCodeCSharp/blob/main/Solutions/Problems/GroupAnagrams.cs) |
1515
| 104 | [Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/) | Easy | [Code](https://github.com/gabaoalb/LeetCodeCSharp/blob/main/Solutions/Problems/MaximumDepthOfBinaryTree.cs) |
16+
| 125 | [Valid Palindrome](https://leetcode.com/problems/valid-palindrome/) | Easy | [Code](https://github.com/gabaoalb/LeetCodeCSharp/blob/main/Solutions/Problems/ValidPalindrome.cs) |
1617
| 128 | [Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/) | Medium | [Code](https://github.com/gabaoalb/LeetCodeCSharp/blob/main/Solutions/Problems/LongestConsecutiveSequence.cs) |
1718
| 217 | [Contains Duplicate](https://leetcode.com/problems/contains-duplicate/) | Easy | [Code](https://github.com/gabaoalb/LeetCodeCSharp/blob/main/Solutions/Problems/ContainsDuplicate.cs) |
1819
| 226 | [Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/) | Easy | [Code](https://github.com/gabaoalb/LeetCodeCSharp/blob/main/Solutions/Problems/InvertBinaryTree.cs) |
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
using Solutions.Problems;
2+
3+
namespace Solutions.Tests.Problems;
4+
5+
public class ValidPalindromeTest
6+
{
7+
public ValidPalindromeSolution Solution { get; } = new();
8+
9+
[Fact]
10+
public void Case1()
11+
{
12+
// Arrange
13+
string s = "A man, a plan, a canal: Panama";
14+
15+
// Act
16+
bool result = Solution.IsPalindrome(s);
17+
18+
// Assert
19+
Assert.True(result);
20+
}
21+
22+
[Fact]
23+
public void Case2()
24+
{
25+
// Arrange
26+
string s = "race a car";
27+
28+
// Act
29+
bool result = Solution.IsPalindrome(s);
30+
31+
// Assert
32+
Assert.False(result);
33+
}
34+
35+
[Fact]
36+
public void Case3()
37+
{
38+
// Arrange
39+
string s = " ";
40+
41+
// Act
42+
bool result = Solution.IsPalindrome(s);
43+
44+
// Assert
45+
Assert.True(result);
46+
}
47+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
namespace Solutions.Problems;
2+
3+
public class ValidPalindromeSolution
4+
{
5+
/// <summary>
6+
/// Reverse string approach to determine if a given string is a palindrome, considering only alphanumeric characters and ignoring cases.
7+
/// Time complexity: O(n), where n is the length of the input string. This is because we need to traverse the string once to clean it and then potentially traverse it again to reverse it.
8+
/// Space complexity: O(n) in the worst case, where n is the length of
9+
/// </summary>
10+
/// <param name="s"></param>
11+
/// <returns></returns>
12+
public bool IsPalindromeReverse(string s)
13+
{
14+
string clean = new([.. s.ToLower().Where(char.IsLetterOrDigit)]);
15+
string reverse = new([.. clean.Reverse()]);
16+
return clean == reverse;
17+
}
18+
19+
/// <summary>
20+
/// Two pointers approach to determine if a given string is a palindrome, considering only alphanumeric characters and ignoring cases.
21+
/// Time complexity: O(n), where n is the length of the input string. This is because we need to traverse the string once to clean it and then potentially traverse it again with the two pointers.
22+
/// Space complexity: O(n) in the worst case, where n is the length of the input string. This occurs when all characters are alphanumeric and need to be stored in the cleaned string. However, if we consider only the additional space used for variables, it is O(1).
23+
/// </summary>
24+
/// <param name="s">The input string to be checked for palindrome properties.</param>
25+
/// <returns>True if the input string is a palindrome, false otherwise.</returns>
26+
public bool IsPalindrome(string s)
27+
{
28+
string clean = new([.. s.ToLower().Where(char.IsLetterOrDigit)]);
29+
(int left, int right) = (0, clean.Length - 1);
30+
31+
while (left < right)
32+
{
33+
if (clean[left] != clean[right]) return false;
34+
left++;
35+
right--;
36+
}
37+
38+
return true;
39+
}
40+
}

0 commit comments

Comments
 (0)