πRust ownership and borrowing
Rust Ownership and Borrowing Practice with HashMap and Vec
Rust has a unique approach to memory management called ownership and borrowing. In Rust, every value has an owner, which is responsible for managing the memory used by the value. When a value goes out of scope, its memory is automatically freed. Let's use a example to practice Rust's ownership and borrowing.
Problem Description
Given two strings ransomNote
and magazine
, return true if ransomNote
can be constructed from magazine
and false otherwise. Each letter in magazine
can only be used once in ransomNote
.
Example 1
Input: ransomNote = "a", magazine = "b"
Output: false
Example 2
Input: ransomNote = "aa", magazine = "ab"
Output: false
Example 3
Input: ransomNote = "aa", magazine = "aab"
Output: true
Constraints
1 <= ransomNote.length, magazine.length <= 10^5
ransomNote
andmagazine
consist of lowercase English letters.
Solutions
According to the problem above, we want to use a container to store the characters in magazine
and check if the characters in randsomNote
are in the container. There are some collection types to store and retrieve data in rust, like:
Sequence:
Vec
,String
,VecDeque
,LinkedList
Maps:
HashMap
,BTreeMap
Sets:
HashSet
,BTreeSet
Misc:
BinaryHeap
Solution with Vec
So, here we can use a Vec
to store the characters in magazine
. The vec
type is a resizable array that stores values in contiguous memory blocks. And some important features of a Vec
are:
A
Vec
can grow or shrink at runtime.Values in a
Vec
can also be fetched using a reference to the collection.
impl Solution {
pub fn can_construct(ransom_note: String, magazine: String) -> bool {
// We create new Vec to store characters in magazine
let mut container:Vec<char> = vec![];
// storing all the characters to the container
for i in magazine.chars(){
container.push(i);
}
// checking all the characters of ransom_note, if are in container and remove it.
for i in ransom_note.chars(){
// retrain() will remove all the elements that are equal to i. It is not a good way to do this if you have `aaaa`.
if let Some(pos)=container.iter().position(|&x| x==i){
container.remove(pos);
}else{
return false;
}
}
true
}
}
Here is a more concise way to do this:
impl Solution {
pub fn can_construct(ransom_note: String, magazine: String) -> bool {
// we can create a iterator with chars()
// and get a collection base on char type with collect()
let mut magazine_vec:Vec<char>=magazine.chars().collect();
// same
for i in ransom_note.chars(){
if let Some(pos)=magazine_vec.iter().position(|&x| x==i){
magazine_vec.remove(pos);
}else{
return false;
}
}
true
}
}
Solution with HashMap
We can also use a HashMap
to store the characters in magazine
. The HashMap
type is a collection of key-value pairs. And some important features of a HashMap
are:
A
HashMap
can grow or shrink at runtime.
Because we will meet the same character in ransomNote
, we can use the character as the key and the number of the character as the value. So, we can use a HashMap<char, i32>
to store the characters in magazine
. And we can use the entry()
method to check if the key is in the HashMap
and update the value.
use std::collections::HashMap;
impl Solution {
pub fn can_construct(ransom_note: String, magazine: String) -> bool {
// create HashMap to store the element in magazine, and we need to handle same character situations. So, we need to use the format like HashMap<char, i32>
let mut hm:HashMap<char,i32>= HashMap::new();
for i in magazine.chars(){
// check if i in HashMap,get_mut() expected a reference
if let Some(value)=hm.get_mut(&i){
// get_mut() return a reference
// value here is a mut reference, *value can be the original element, an integer
*value+=1;
}else{
hm.insert(i,1);
}
}
for i in ransom_note.chars(){
// same to above
if let Some(value) =hm.get_mut(&i){
*value=*value-1;
if *value<0{
return false;
}
}else{
return false;
}
}
true
}
}
Here is a more concise way to do this:
impl Solution {
pub fn can_construct(ransom_note: String, magazine: String) -> bool {
// We create new HashMap to store characters in magazine
let mut container:HashMap<char, i32> = HashMap::new();
// storing all the characters to the container
for i in magazine.chars(){
// entry() will return a mutable reference to the value corresponding to the key
// and insert the key with value 0 if it is not exist,
// then we use the deference operator * to modiy the value by adding 1 to it.
*container.entry(i).or_insert(0)+=1;
}
// checking all the characters of ransom_note, if are in container and remove it.
for i in ransom_note.chars(){
if let Some(x)=container.get_mut(&i){
*x-=1;
if *x<0{
return false;
}
}else{
return false;
}
}
true
}
}
Conclusion
In my opinion, we do not need to scare the ownership and borrowing. We just need to know that we can use &
to borrow a reference to the value and use &mut
to borrow a mutable reference to the value. And we can use &
and &mut
to pass the value to a function etc. *
to dereference a reference. In another word, it is to get the value from a reference. And we can use *
to get the value from a mutable reference and change the value.
Last updated
Was this helpful?