Few questions on Strings

1. Ransom note problem

You are given a note - which is a string, and a magazine paper - which is also a string. Your goal is to determine whether the given note can be constructed from the magazine. When you use one occurrence of a letter from the magazine, you cannot reuse it again.

Solution: Treat the note and magazine like a bag-of-letters.

What Data Structure should I use?:

  • Two dictionaries to hold the frequency of occurence of these letters.

What is my Algorithm?: The trick here is to iterate over note dictionary while comparing the values in magazine dictionary. Inside this loop we check if any of these two conditions are met, if they are met, then return False otherwise outside the loop return True.

  • Does magazine have the letter in note?
  • Is magazine’s letter count less than note’s letter count?
def ransom_note(note, magazine):

    # initialize
    note_dict = {}
    magazine_dict = {}

    # iterate over the inputs
    for letter in note:
        if note_dict.get(letter) is None:
            note_dict[letter] = 1
        else:
            note_dict[letter] += 1

    for letter in magazine:
        if magazine_dict.get(letter) is None:
            magazine_dict[letter] = 1
        else:
            magazine_dict[letter] += 1

    # two conditions:
    for letter, freq in note_dict.items():
        if magazine_dict.get(letter) is None or magazine_dict[letter] < freq:
            return False

    return True
note1 = "shravan"
note2 = "hellob"
magazine = "hello worldbshavan"
print(ransom_note(note1, magazine))
print(ransom_note(note2, magazine))
True
True

2. First Unique Character in a String

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Solution:

  • sort the string
  • iterate over sorted string
    • skip over if current value = next value

Wrong approach.

Right approach:

  • Use a dictionary. The logic we are going to use is, if we see that letter for the first time, then we store its index. If we are seeing that letter for the second time, then we are going to store -1.

In this way, our dictionary will look like: {l:0, e:-1, t:3, c:4, o:5, d:6}

Then, we need pick the key with the lowest value.

s1 = 'leetcode' # 0
s2 = 'leetlode' # 3
s3 = 'sshhrrk'
def first_unique(string):
    # define a dict
    s_dict = {}

    # build a dictionary {l:0, e:-1, t:3, c:4, o:5, d:6}
    for index, letter in enumerate(string):
        if s_dict.get(letter) is None:
            s_dict[letter] = index
        else:
            s_dict[letter] = -1

    # sort the dictionary by value in ascending
    sorted_dict = sorted(s_dict.items(), key=lambda x: x[1])

    # pick the first index which is not -1
    for letter, index in sorted_dict:
        if index != -1:
            return index

    # not found any unique chars
    return -1
print(first_unique(s1))
print(first_unique(s2))
print(first_unique(s3))
0
3
6

3. Reorder Data in Log files

You have an array of logs. Each log is a space delimited string of words.

For each log, the first word in each log is an alphanumeric identifier. Then, either:

  • Each word after the identifier will consist only of lowercase letters, or;
  • Each word after the identifier will consist only of digits.

We will call these two varieties of logs letter-logs and digit-logs. It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log. The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties. The digit-logs should be put in their original order.

Return the final order of the logs.

Example:

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

Solution: We will have 2 lists, one will hold the letter-logs and the second will hold digit-logs.

What is the data structure?: 2 lists

What is the algorithm?:

  • Iterate over logs, and create letter-logs and digit-logs lists.
  • Sort letter-logs such that if the first log value is same, then use identifier.
  • Merge the lists
logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
def reorder_log_data(logs):

    # define data structures
    letter_logs = []
    digit_logs = []

    # iterate over the logs
    for log in logs:
        # as per problem statement, we have atleast one word after identifier
        if log.split()[1].isalpha():
            letter_logs.append(log)
        else:
            digit_logs.append(log)

    #sorted_letter_logs = sorted(letter_logs, key=lambda x:x[0])
    letter_logs.sort(key=lambda x:x[0])
    for item in letter_logs:
        print(item.split()[1:])
    #sorted_letter_id_logs = sorted(sorted_letter_logs, key=lambda x:x[1:])
    letter_logs.sort(key=lambda x:x.split()[1:])
    print(letter_logs)
reorder_log_data(logs)
['art', 'can']
['own', 'kit', 'dig']
['art', 'zero']
['let1 art can', 'let3 art zero', 'let2 own kit dig']
def reorder_log_data(logs):

    # define data structures
    letter_logs = []
    digit_logs = []

    # iterate over the logs
    for log in logs:
        # as per problem statement, we have atleast one word after identifier
        if log.split()[1].isalpha():
            letter_logs.append(log)
        else:
            digit_logs.append(log)

    letter_logs.sort(key=lambda x:x[0])
    letter_logs.sort(key=lambda x:x.split()[1:])

    return [*letter_logs, *digit_logs]
reorder_log_data(logs)
['let1 art can',
 'let3 art zero',
 'let2 own kit dig',
 'dig1 8 1 5 1',
 'dig2 3 6']

4. Robot return to origin

There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.

The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after it finishes all of its moves, return true. Otherwise, return false.

Note: The way that the robot is “facing” is irrelevant. “R” will always make the robot move to the right once, “L” will always make it move left, etc. Also, assume that the magnitude of the robot’s movement is the same for each move.

Example:

Input: "UD"
Output: true
Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.

Example:

Input: "LL"
Output: false
Explanation: The robot moves left twice. It ends up two "moves" to the left of the origin. We return false because it is not at the origin at the end of its moves.

Answer: The best way to approach this problem is by taking examples first.

  • RLLR (True)
  • RUUDDL (True)
  • RRL (False)
  • UUD (False)

Two conditions have to be met:

  • Number of Rs and Ls has to be same.
  • Number of Us and Ds has to be same.

Data Structure: I will use a dictionary to keep track of the number of times each letter occurs.

Algorithm: If both the above conditions are met, return True otherwise False.

def robot_to_origin(path):

    # define the dict
    robo_dict = {}

    # iterate over path and get freq
    for letter in path:
        if robo_dict.get(letter) is None:
            robo_dict[letter] = 1
        else:
            robo_dict[letter] += 1

    print(robo_dict)
    lr_balance = False
    ud_balance = False

    # check the above two conditions
    if robo_dict.get('R') and robo_dict.get('L'):
        if robo_dict['R'] == robo_dict['L']:
            lr_balance = True
    elif robo_dict.get('R') or robo_dict.get('L'):
            lr_balance = False
    else:
        lr_balance = True

    if robo_dict.get('U') and robo_dict.get('D'):
        if robo_dict['U'] == robo_dict['D']:
            ud_balance = True
    elif robo_dict.get('U') or robo_dict.get('D'):
        ud_balance = False
    else:
        ud_balance = True

    return lr_balance and ud_balance
s1 = 'RLLR'
s2 = 'RUUDDL'
s3 = 'RRL'
s4 = 'RLL'
s5 = 'RR'
s6 = ''
robot_to_origin(s1)
{'R': 2, 'L': 2}





True
robot_to_origin(s2)
{'R': 1, 'U': 2, 'D': 2, 'L': 1}





True
robot_to_origin(s3)
{'R': 2, 'L': 1}





False
robot_to_origin(s4)
{'R': 1, 'L': 2}





False
robot_to_origin(s5)
{'R': 2}





False
robot_to_origin(s6)
{}





True

Simple Solutions:

import collections
def judgeCircle(moves):
    c = collections.Counter(moves)
    return c['L'] == c['R'] and c['U'] == c['D']
print(judgeCircle(s1))
print(judgeCircle(s2))
print(judgeCircle(s3))
print(judgeCircle(s4))
print(judgeCircle(s5))
print(judgeCircle(s6))
True
True
False
False
False
True

Another solution:

Intuition: We can simulate the position of the robot after each command.

Algorithm: Initially, the robot is at (x, y) = (0, 0). If the move is ‘U’, the robot goes to (x, y-1); if the move is ‘R’, the robot goes to (x, y) = (x+1, y), and so on.

def judgeCircle(moves):
    x = y = 0
    for move in moves:
        if move == 'U': y -= 1
        elif move == 'D': y += 1
        elif move == 'L': x -= 1
        elif move == 'R': x += 1

    return x == y == 0
print(judgeCircle(s1))
print(judgeCircle(s2))
print(judgeCircle(s3))
print(judgeCircle(s4))
print(judgeCircle(s5))
print(judgeCircle(s6))
True
True
False
False
False
True

5. Reverse words in a string

Given an input string, reverse the string word by word.

Example 1:

Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: "  hello world!  "
Output: "world! hello"

Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: "a good   example"
Output: "example good a"

Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Solution:

  • Start by creating a list of tokens.
  • Discard tokens that are not alphanumeric
  • Iterate from end of the list and build a new list
  • Use join to stitch the string together
def reverse_words(sentence):

    # tokenize
    sentence = [word for word in sentence.split() if word != ' ']

    # iterate
    return ' '.join(sentence[::-1])
s1 = "the sky is blue"
s2 = "  hello world!  "
s3 = "a good   example"
s4 = ""
s5 = "a  adfasd as       $ $$ b"
print(reverse_words(s1))
print(reverse_words(s2))
print(reverse_words(s3))
print(reverse_words(s4))
print(reverse_words(s5))
blue is sky the
world! hello
example good a

b $$ $ as adfasd a

Tags:

Updated: