Homework 01 Solved

Description

Problem 1

There are three kinds of parentheses:

• (, )

• f, g

• [, ]

Given a string, write a function called matching_parentheses that checks if the parentheses in it match, i.e.,

• open brackets are closed by the same kind of closing brackets; and

• open brackets are closed in the correct order.

Your function should return true if the parentheses match, false otherwise. The input string may contain any of the parentheses and alphabetical letters. (Return true if the input string is empty. You may assume the strings are not too long.)

Language: Write the function in C++, Python, and Rust. You may use whichever you are most comfortable with as the first language. (See syllabus for details.)

Note on Rust:

• There are two kinds of strings in Rust: string literal (&str) and string object (String). For more

details: check

– https://www.tutorialspoint.com/rust/rust_string.htm

– https://stackoverflow.com/questions/24158114/what-are-the-differences-between-rusts-strin

• Based on the description of the problem, &str would be more appropriate since the input never changes. But String is easier to work with so we will use that.

• Input type: String

Output type: bool

Examples:

1. Input: ()

Output: true

2. Input: [a(b)]

Output: true

3. Input: [a(b])

Output: false

4. Input: afabc([])

Output: false

5. Input: aabc([])gc

Output: false

Problem 2

Given an array of strings, we want to find the longest common prefix of the strings. For example, given an array of strings [“apple”, “app”, “aple”, “appl”], the longest common prefix is “ap”. If the strings do not have any common prefix, return the empty string.

Language: Write the function in C++, Python, and Rust. You may use whichever you are most comfortable with as the first language. (See syllabus for details.)

• C++:

Input type: vector<String>&

Output type: String

• Rust:

Input type: Vec<String>

Output type: String

2