8000 palindrome · jhideki/rust_leetcode@8c7356d · GitHub
[go: up one dir, main page]
Skip to content

Commit 8c7356d

Browse files
jhidekijhideki
committed
palindrome
1 parent a43ec4c commit 8c7356d

File tree

3 files changed

+70
-1
lines changed

3 files changed

+70
-1
lines changed

‎src/house_robber2.rs

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn rob(nums: Vec<i32>) -> i32 {
4+
if nums.len() == 1 {
5+
return nums[0];
6+
} else if nums.len() == 0 {
7+
return 0;
8+
}
9+
std::cmp::max(
10+
Self::r(&nums[1..nums.len()]),
11+
Self::r(&nums[0..nums.len() - 1]),
12+
)
13+
}
14+
15+
fn r(nums: &[i32]) -> i32 {
16+
let (mut r1, mut r2) = (0, 0);
17+
for val in nums {
18+
let temp = std::cmp::max(r1 + val, r2);
19+
r1 = r2;
20+
r2 = temp;
21+
}
22+
std::cmp::max(r1, r2)
23+
}
24+
}

‎src/longest_palindromic.rs

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
use std::ops::RangeInclusive;
2+
pub struct Solution {}
3+
impl Solution {
4+
pub fn longest_palindrome(s: String) -> String {
5+
let s = s.as_str();
6+
(0..s.len())
7+
.fold("", |current_longest, idx| {
8+
current_longest
9+
.longest(s.longest_palindrome_around(idx..=idx))
10+
.longest(s.longest_palindrome_around(idx..=idx + 1))
11+
})
12+
.into()
13+
}
14+
}
15+
16+
trait LongestPalindrome {
17+
type Idx;
18+
fn longest_palindrome_around(&self, center: RangeInclusive<Self::Idx>) -> &Self;
19+
fn longest<'a>(&'a self, other: &'a Self) -> &'a Self;
20+
}
21+
impl LongestPalindrome for str {
22+
type Idx = usize;
23+
fn longest_palindrome_around(&self, center: RangeInclusive<Self::Idx>) -> &Self {
24+
let (mut start, mut end) = center.into_inner();
25+
let characters = self.as_bytes();
26+
loop {
27+
if characters.get(start) != characters.get(end) {
28+
return &self[start + 1..end];
29+
}
30+
if let (Some(new_start), Some(new_end)) = (start.checked_sub(1), end.checked_add(1)) {
31+
start = new_start;
32+
end = new_end;
33+
} else {
34+
return &self[start..=end];
35+
}
36+
}
37+
}
38+
fn longest<'a>(&'a self, other: &'a Self) -> &'a Self {
39+
if self.len() > other.len() {
40+
self
41+
} else {
42+
other
43+
}
44+
}
45+
}

‎src/main.rs

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,2 +1,2 @@
1-
mod house_robber;
1+
mod longest_palindromic;
22
fn main() {}

0 commit comments

Comments
 (0)
0