Question
#![allow(unused)]
fn main() {
impl Solution
{
pub fn length_of_longest_substring(s: String) -> i32
{
let mut max_len: usize = 0;
// [1] longest substring is the one with the largest
// difference between positions of repeated characters;
// thus, we should create a storage for such positions
let mut pos: [usize;128] = [0;128];
// [2] while iterating through the string (i.e., moving
// the end of the sliding window), we should also
// update the start of the window
let mut start: usize = 0;
for (end, ch) in s.chars().enumerate()
{
// [3] get the position for the start of sliding window
// with no other occurences of 'ch' in it
start = start.max(pos[ch as usize]);
// [4] update maximum length
max_len = max_len.max(end-start+1);
// [5] set the position to be used in [3] on next iterations
pos[ch as usize] = end + 1;
}
return max_len as i32;
}
}
}
Question
#![allow(unused)]
fn main() {
impl Solution {
pub fn longest_palindrome(s: String) -> String {
// Convert string to char vector
let s_chars: Vec<char> = s.chars().collect();
let mut left = 0;
let mut right = 0;
// Expand around the center
fn expand(s: &Vec<char>, mut i: isize, mut j: isize, left: &mut usize, right: &mut usize) {
while i >= 0 && j < s.len() as isize && s[i as usize] == s[j as usize] {
if (j - i) as usize > *right - *left {
*left = i as usize;
*right = j as usize;
}
i -= 1;
j += 1;
}
}
for i in 0..s.len() {
// Odd length palindrome
expand(&s_chars, i as isize, i as isize, &mut left, &mut right);
// Even length palindrome
expand(&s_chars, i as isize, i as isize + 1, &mut left, &mut right);
}
// Return the longest palindrome substring
s_chars[left..=right].iter().collect()
}
}
}
Question
#![allow(unused)]
fn main() {
impl Solution {
pub fn convert(s: String, num_rows: i32) -> String {
let mut zigzags: Vec<_> = (0..num_rows)
.chain((1..num_rows-1).rev())
.cycle()
.zip(s.chars())
.collect();
zigzags.sort_by_key(|&(row, _)| row);
zigzags.into_iter()
.map(|(_, c)| c)
.collect()
}
}
}
Question
#![allow(unused)]
fn main() {
impl Solution {
pub fn my_atoi(s: String) -> i32 {
let s = s.trim_start();
let (s, sign) = match s.strip_prefix('-') {
Some(s) => (s, -1),
None => (s.strip_prefix('+').unwrap_or(s), 1),
};
s.chars()
.map(|c| c.to_digit(10))
.take_while(Option::is_some)
.flatten()
.fold(0, |acc, digit| {
acc.saturating_mul(10).saturating_add(sign * digit as i32)
})
}
}
}
Question
#![allow(unused)]
fn main() {
impl Solution {
pub fn is_match(s: String, p: String) -> bool {
let s: &[u8] = s.as_bytes();
let p: &[u8] = p.as_bytes();
let m = s.len();
let n = p.len();
let mut dp = vec![vec![false; n + 1]; m + 1];
dp[0][0] = true;
for j in 1..=n {
if p[j - 1] == b'*' {
dp[0][j] = dp[0][j - 2];
}
}
for i in 1..=m {
for j in 1..=n {
if p[j - 1] == b'.' || p[j - 1] == s[i - 1] {
dp[i][j] = dp[i - 1][j - 1];
} else if p[j - 1] == b'*' {
dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == b'.'));
}
}
}
dp[m][n]
}
}
}
Question
#![allow(unused)]
fn main() {
const ONES : [&str;10] = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
const TENS : [&str;10] = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
const CENT : [&str;10] = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
const MILS : [&str;4] = ["", "M", "MM", "MMM"];
impl Solution
{
pub fn int_to_roman(num: i32) -> String
{
// Given that the number of outcomes is small, a brute force
// substituion for each power of ten is a viable solution...
format!("{}{}{}{}", MILS[(num / 1000 % 10) as usize],
CENT[(num / 100 % 10) as usize],
TENS[(num / 10 % 10) as usize],
ONES[(num % 10) as usize])
}
}
}
Question
Solution Explanation
#![allow(unused)]
fn main() {
impl Solution {
pub fn full_justify(words: Vec<String>, max_width: i32) -> Vec<String> {
let mut res = Vec::new();
let mut cur = Vec::new();
let mut num_of_letters: i32 = 0;
for word in &words {
if word.len() as i32 + cur.len() as i32 + num_of_letters > max_width {
for i in 0..(max_width - num_of_letters) {
let idx = i as usize % (if cur.len() > 1 { cur.len() - 1 } else { cur.len() });
cur[idx] = format!("{} ", cur[idx]);
}
res.push(cur.join(""));
cur.clear();
num_of_letters = 0;
}
cur.push(word.clone());
num_of_letters += word.len() as i32;
}
let last_line = cur.join(" ");
res.push(format!("{:<width$}", last_line, width=max_width as usize));
res
}
}
}
question
#![allow(unused)]
fn main() {
impl Solution {
pub fn simplify_path(path: String) -> String {
let mut simplified_path = vec![];
for dir in path.split('/') {
match dir {
"" | "." => continue,
".." => { simplified_path.pop(); }
_ => simplified_path.push(dir),
}
}
"/".to_owned() + &simplified_path.join("/")
}
}
}
Question
Solution link
#![allow(unused)]
fn main() {
//Naive Recursion - TLE
fn _min_distance(word1: &[char], word2: &[char]) -> i32 {
if word1.is_empty() {
return word2.len() as i32;
}
if word2.is_empty() {
return word1.len() as i32;
}
if word1[0] == word2[0] {
return _min_distance(&word1[1..], &word2[1..]);
}
let insert = _min_distance(&word[1..], word2);
let delete = _min_distance(word1, &word2[1..]);
let replace = _min_distance(&word1[1..], &word2[1..])
1 + std::cmp::min(insert, std::cmp::min(delete, replace))
}
impl Solution {
pub fn min_distance(word1: String, word2: String) -> i32 {
_min_distance(
&word1.chars().collect::<Vec<char>>(),
&word2.chars().collect::<Vec<char>>(),
)
}
}
}
#![allow(unused)]
fn main() {
//Memoization - Top Down
fn _min_distance(word1: &[char], word2: &[char], memo: &mut [Vec<i32>], i: usize, j: usize) -> i32 {
if word1.is_empty() {
return word2.len() as i32;
}
if word2.is_empty() {
return word1.len() as i32;
}
if memo[i][j] != -1 {
return memo[i][j];
}
if word1[0] == word2[0] {
memo[i][j] = _min_distance(&word1[1..], &word2[1..], memo, i + 1, j + 1);
} else {
let insert = _min_distance(&word[1..], word2, memo, i + 1, j);
let delete = _min_distance(word1, &word2[1..], memo, i, j + 1);
let replace = _min_distance(&word1[1..], &word2[1..], memo, i + 1, j + 1)
memo[i][j] = 1 + std::cmp::min(insert, std::cmp::min(delete, replace))
}
memo[i][j]
}
impl Solution {
pub fn min_distance(word1: String, word2: String) -> i32 {
_min_distance(
&word1.chars().collect::<Vec<char>>(),
&word2.chars().collect::<Vec<char>>(),
&mut vec![vec![-1; word2.len()]; word1.len()],
0,
0,
)
}
}
}
#![allow(unused)]
fn main() {
//Tabulation - bottom up
impl Solution {
pub fn min_distance(word1: String, word2: String) -> i32 {
let m = word1.len();
let n = word2.len();
let word1: Vec<char> = word1.chars().collect();
let word2: Vec<char> = word2.chars().collect();
let mut dp: Vec<Vec<i32>> = vec![vec![0; n + 1]; m + 1];
for i in 0..m {
dp[i][n] = (m - i) as i32;
}
for j in 0..n {
dp[m][j] = (n - j) as i32;
}
for i in (0..m).rev() {
for j in (0..n).rev() {
if word1[i] == word2[j] {
dp[i][j] = dp[i + 1][j + 1];
} else {
dp[i][j] =
1 + std::cmp::min(dp[i + 1][j + 1], std::cmp::min(dp[i + 1][j], dp[i][j + 1]));
}
}
}
dp[0][0]
}
}
}
#![allow(unused)]
fn main() {
//Tabulation with space optimization
impl Solution {
pub fn min_distance(word1: String, word2: String) -> i32 {
let m = word1.len();
let n = word2.len();
let word1: Vec<char> = word1.chars().collect();
let word2: Vec<char> = word2.chars().collect();
// We only store 2 rows at a time
let mut dp_bottom_row: Vec<i32> = (0..(n + 1)).map(|j| (n - j) as i32).collect();
let mut dp_top_row = vec![1; n + 1];
for i in (0..m).rev() {
for j in (0..n).rev() {
if word1[i] == word2[j] {
dp_top_row[j] = dp_bottom_row[j + 1];
} else {
dp_top_row[j] = 1 + std::cmp::min(dp_bottom_row[j + 1], std::cmp::min(dp_bottom_row[j], dp_top_row[j + 1]));
}
}
// Swap the 2 rows and move to the next
dp_bottom_row.copy_from_slice(&dp_top_row);
dp_top_row[n] = (m - i + 1) as i32;
}
dp_bottom_row[0]
}
}
}
Question
pub fn maximize_greatness(mut nums: Vec<i32>) -> i32 {
nums.sort();
let n = nums.len();
let (mut ans, mut l, mut r) = (0, 0, n);
for i in 0..n-1 {
r = n;
l += 1;
while l < r {
let mid = l + (r - l) / 2;
if nums[mid] > nums[i] { r = mid }
else { l = mid + 1 };
}
if l < n && nums[l] > nums[i] { ans += 1 }
else { break };
}
ans
}
}