Adventures in Leetcode: PowerShell + Leetcode
PowerShell, Leetcode ·Adventures in Leet Code: PowerShell Twist
I’ve been looking into new challenges recently and decided to give LeetCode a shot. I quickly realized that I haven’t been working on this kind of problem since I took a couple programming classes where I didn’t learn much. Leetcode doesn’t support PowerShell, so I’m going to post these here and if anyone has any constructive feedback I’d appreciate it if you shared it in the comments below.
I found that I was having to look up things that I haven’t encountered much while using PowerShell. I really enjoy how these are pushing me to grow. This blog post aims to share some problems and solutions that I’ve worked on.
Useful Constructs
For Loops
A For loop is a great way to iterate on a subset of a collection of items. Oftentimes, foreach is more appropriate, but I’ve found the for loop to be useful in a lot of leetcode questions.
# Reverse a string with a for loop
$string = 'Jill loves cars.'
# make sure to use the length property instead of count when dealing with manipulating characters in a string
$output = for ($i = 1 ; $i -le $string.length; $i++) {
$string[-$i] # output each character, starting at the back
}
# $output is an array, rather than a string. We need to -join them back together again <3
$output -join ''
Problems
Add Binary Strings
Given two binary strings a and b, return their sum as a binary string.
Example 1:
Input: a = “11”, b = “1” Output: “100”
My Solution
function Convert-BinaryStringtoInteger {
[CmdletBinding()]
param(
[Parameter(Mandatory)]
[int]$a,
[Parameter(Mandatory)]
[int]$b
)
$aInt = [Convert]::ToInt32($a,2)
$bInt = [Convert]::ToInt32($b,2)
$cInt = $aInt + $bInt
$cBinaryString = [Convert]::ToString($cInt,2)
Write-Output $cBinaryString
}
Test it
Convert-BinaryStringtoInteger -a 11 -b 1
100
Convert-BinaryStringtoInteger -a 1010 -b 1011
10101
2 - Remove All Adjacent Duplicates In String
Problem
https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/
Remove All Adjacent Duplicates In String. You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.
My Solution
function Remove-AdjacentDuplicates {
param(
[Parameter(Mandatory)]
[ValidateScript({
if (-not ($_ -cmatch '[a-z]')) {
throw 'lowercase English letters only'
}
else { $true }
})]
[ValidateLength(1, 100000)]
[string]
$s
)
for ($i = 0; $i -lt $s.length ; $i++) {
if ($s[$i] -eq $s[$i + 1]) {
$stringToReplace = "$($s[$i])$( $s[ $i + 1 ])"
$s = $s.replace($stringtoReplace, '')
$i = -1 # set to negative because it get +1 every iteration and we want it to be on 0
}
}
Write-Output $s
}
Test it
Remove-AdjacentDuplicates -s abbaca
ca
Remove-AdjacentDuplicates -s azxxzy
ay
3 - Valid Word Abbreviation
https://leetcode.com/problems/valid-word-abbreviation/
Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation.
A substring is a contiguous non-empty sequence of characters within a string.
My Solution
function Test-ValidWordAbbreviation {
param(
[Parameter(Mandatory)]
[ValidateLength(1, 20)]
[ValidateScript({
if ($_ -cmatch '[a-z]0') {
throw "No leading zeros"
}
if ($_ -cmatch '[A-Z]') {
throw "No capital letters"
}
else { $true }
})]
[string]$Word,
[Parameter(Mandatory)]
[ValidateLength(1, 10)]
[string]$Abbr
)
$replacedAbbr = $Abbr
$pattern = '\d{1,}' # 1 or more digits
$matches = [regex]::Matches($replacedAbbr , $pattern)
for ($i = 0; $i -lt $matches.Count; $i++) {
$numbers = [regex]::Matches($replacedAbbr , $pattern)
[int]$upperBound = $numbers[0].Index + $numbers[0].value - 1
$replacementText = $word[ $numbers[0].index..$upperBound ] -join ''
$replacedAbbr = $replacedAbbr.Replace( $numbers[0].Value , $replacementText )
}
if ($replacedAbbr -eq $Word) { Write-Output $true }
else { Write-Output $false }
}
Test it
Test-ValidWordAbbreviation -Word internationalization -Abbr i12iz4n
True
Test-ValidWordAbbreviation -Word a2e -Abbr apple
False
4 - Valid Palindrome II
https://leetcode.com/problems/valid-palindrome-ii/
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
My Solution
function Test-ValidPalindromeII {
param(
[Parameter(Mandatory)]
[ValidateLength(1, 100000)]
[ValidateScript({
if ($_ -cmatch '[A-Z]') {
throw 'lowercase English letters only'
}
else {
Write-Output $true
}
})]
[string]
$s
)
# See if it's a palindrome as-is
$reversedWord = for ($j = 1; $j -le $s.length; $j++) {
$s[ - $j ]
}
$reversedWord = $reversedWord -join ''
if ($reversedWord -eq $s) { $Palindrome = $true }
# Iterate through and remove a character then test if it's a palindrome
for ($i = 0; $i -lt $s.length; $i++) {
# break from loop if $Palindrome is set to $true
if ($Palindrome) { break }
$replacedWord = $s.remove($i, 1)
$reversedWord = for ($j = 1; $j -le $replacedWord.length; $j++) {
$replacedWord[ - $j ]
}
$reversedWord = $reversedWord -join ''
if ($reversedWord -eq $replacedWord) {
$Palindrome = $true
}
}
if ($Palindrome) {
Write-Output $true
}
else { Write-Output $false }
}
Test it
Test-ValidPalindromeII -s 'aba'
True
Test-ValidPalindromeII -s 'abca'
True
Test-ValidPalindromeII -s 'abc'
False
5 - Valid Phone Number
https://www.interviewbit.com/problems/valid-phone-number/
Given a text file input that contains list of phone numbers (one per line).
Write a bash script to print all valid phone numbers.You may assume that a valid phone number must appear in one of the following two formats:
(xxx) xxx-xxxx xxx-xxx-xxxx You may also assume each line in the text file must not contain leading or trailing white spaces.
function Get-ValidPhoneNumber {
param(
[Parameter(Mandatory)]
[string[]]$Numbers
)
foreach($number in $Numbers){
if ($number -match '^\(\d{3}\) \d{3}-\d{4}$'){
Write-Output $number
}
if ($number -match '^\d{3}-\d{3}-\d{4}$') {
Write-Output $number
}
}
}
Test It
$numbers = "987-123-4567", "123 456 7890","(123) 456-7890"
Get-ValidPhoneNumber -Numbers $numbers
6 - Lines in a given range
Write a bash script to print all the lines of the input which are in the given range. The first line of the input contains two integers l and r separated by space. You have to print all the lines of the file input which are in the range of [l, r].
function Get-LinesinGivenRange {
param(
[Parameter(Mandatory)]
[string[]]
$InputContent
)
$ranges = ($InputContent -split "`n")[0].trim() -split ' '
$InputContent = $InputContent -split "`n"
$InputContent[( $range[0] -1 )..( $range[1] -1 )]
}
Test It
$content = "10 15
Line 2
Line 3
Line 4
Line 5
Line 6
Line 7
Line 8
Line 9
Line 10
Line 11
Line 12
Line 13
Line 14
Line 15
Line 16
Line 17
Line 18
Line 19
Line 20"
Get-LinesinGivenRange -Input $content -Range 10,15
7 - Remove Punctuations
https://www.interviewbit.com/problems/remove-punctuations/
Write a bash script that removes all the punctuations in the given file named input For this question, assume that all of the following symbols are punctuations: ! @ # $ % ^ & * ( ) _ - + = { } [ ] ; : ‘ “ ` / > ? . , < ~ | \
Example:
Assume that input has the following content:
This’s the sunny day. It is the sunny day, we can go out. Your script should output the following:
Thiss the sunny day It is the sunny day we can go out
My Solution
function Remove-Punctuation {
param(
[Parameter(Mandatory)]
[string]
$InputContent
)
$characters = '!', '@', '#', '$', '%', '^', '&', '*', '(', ')', '_', '-', '+', '=', '{', '}', '[', ']', ';', ':', "'", '"', '`', '/', '>', '?', '.', ',', '<', '~', '|', '\'
$characters | Foreach-Object {
$InputContent = $InputContent.replace($_, '')
}
Write-Output $InputContent
}
Test it
$string = "This's the sunny day.
It is the sunny day, we can go out."
Remove-Punctuation -InputContent $string
Thiss the sunny day
It is the sunny day we can go out
8 - Majority Element
https://www.interviewbit.com/problems/majority-element
Given an array of size n, find the majority element. The majority element is the element that appears more than floor(n/2) times. You may assume that the array is non-empty and the majority element always exist in the array.
Example :
Input : [2, 1, 2] Return : 2 which occurs 2 times which is greater than 3/2.
My solution
function Get-Solution {
[CmdletBinding()]
param (
[int[]]$Numbers
)
$numbers | Where-Object {$_ -gt ($Numbers.count / 2) } | Select-Object -First 1
}
Test It
Get-Solution -Numbers 2,1,2
2
9 - Reverse Words in a String
https://leetcode.com/problems/reverse-words-in-a-string/
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
My Solution
function Reverse-WordsinString {
[CmdletBinding()]
param(
[Parameter(Mandatory)]
[string]$S
)
$words = ($S -split ' ').trim() # Split the words and remove extra spaces
# the skye is blue
$output = for ($i = 1; $i -le $words.count; $i++){
$words[-$i] | Where-Object {$_ -Match '\w'} # only grab words, not blank lines
}
$output -join ' '
}
Test It
Reverse-WordsinString -S "the skye is blue"
blue is skye the
Reverse-WordsinString -S " Bob Loves Alice "
Alice Loves Bob
Reverse-WordsinString -S "Alice does not even like bob"
bob like even not does Alice
10 - Word Break
https://leetcode.com/problems/word-break/
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = “leetcode”, wordDict = [“leet”,”code”] Output: true Explanation: Return true because “leetcode” can be segmented as “leet code”. Example 2:
Input: s = “applepenapple”, wordDict = [“apple”,”pen”] Output: true Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”. Note that you are allowed to reuse a dictionary word. Example 3:
Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”] Output: false
My Solution
function Test-WordBreak {
[CmdletBinding()]
param(
[Parameter(Mandatory)]
[string]$s,
[Parameter(Mandatory)]
[string[]]$WordDict
)
$remainingWords = $s
foreach ($word in $WordDict ) {
$remainingWords = $remainingWords -split $word
}
if ( ( $remainingWords | Where-Object { $_ -match '\w' }) -gt 0) {
return $false
}
else {
return $true
}
}
Test it
test-wordbreak -s leetcode -worddict 'leet','code'
True
test-wordbreak -s applepenapple -worddict 'apple','pen'
True
test-wordbreak -s catsandog -WordDict 'cats','dog','sand','and','cat'
False