Rust每日一练(Leetday0031) 解码方法、复原 IP 地址

package main
import (
  "fmt"
)
func numDecodings(s string) int {
  n := len(s)
  if n == 0 {
    return 0
  }
  dp := make([]int, n+1)
  dp[0] = 1
  if s[0] == '0' {
    dp[1] = 0
  } else {
    dp[1] = 1
  }
  for i := 2; i <= n; i++ {
    if s[i-1] != '0' {
      dp[i] = dp[i-1]
    }
    if s[i-2] == '1' || (s[i-2] == '2' && s[i-1] >= '0' && s[i-1] <= '6') {
      dp[i] += dp[i-2]
    }
  }
  return dp[n]
}
func main() {
  fmt.Println(numDecodings("12"))
  fmt.Println(numDecodings("226"))
  fmt.Println(numDecodings("0"))
}

package main
import (
  "fmt"
)
func numDecodings(s string) int {
  n := len(s)
  if n == 0 {
    return 0
  }
  prev1, prev2 := 1, 0
  if s[0] == '0' {
    prev1, prev2 = 0, 0
  } else {
    prev1, prev2 = 1, 1
  }
  for i := 2; i <= n; i++ {
    cur := 0
    if s[i-1] != '0' {
      cur = prev1
    }
    if s[i-2] == '1' || (s[i-2] == '2' && s[i-1] >= '0' && s[i-1] <= '6') {
      cur += prev2
    }
    prev1, prev2 = cur, prev1
  }
  return prev1
}
func main() {
  fmt.Println(numDecodings("12"))
  fmt.Println(numDecodings("226"))
  fmt.Println(numDecodings("0"))
}

package main
import (
  "fmt"
)
func numDecodings(s string) int {
  n := len(s)
  memo := make([]int, n)
  return dfs(s, 0, memo)
}
func dfs(s string, start int, memo []int) int {
  if start == len(s) {
    return 1
  }
  if memo[start] != 0 {
    return memo[start]
  }
  res := 0
  if s[start] != '0' {
    res += dfs(s, start+1, memo)
  }
  if start+1 < len(s) && (s[start] == '1' || (s[start] == '2' && s[start+1] >= '0' && s[start+1] <= '6')) {
    res += dfs(s, start+2, memo)
  }
  memo[start] = res
  return res
}
func main() {
  fmt.Println(numDecodings("12"))
  fmt.Println(numDecodings("226"))
  fmt.Println(numDecodings("0"))
}

fn restore_ip_addresses(s: &String) -> Vec<String> {
    let mut res = Vec::new();
    if s.len() < 4 || s.len() > 12 {
        return res;
    }
    for a in 1..=3 {
        for b in 1..=3 {
            for c in 1..=3 {
                for d in 1..=3 {
                    if a + b + c + d == s.len() {
                        let s1 = &s[0..a];
                        let s2 = &s[a..a+b];
                        let s3 = &s[a+b..a+b+c];
                        let s4 = &s[a+b+c..];
                        if is_valid(&s1) && is_valid(&s2) && is_valid(&s3) && is_valid(&s4) {
                            let ip = format!("{}.{}.{}.{}", s1, s2, s3, s4);
                            res.push(ip);
                        }
                    }
                }
            }
        }
    }
    res
}
fn is_valid(s: &str) -> bool {
    if s.len() > 1 && s.chars().nth(0).unwrap() == '0' {
        return false;
    }
    true
}
fn main() {
    let s = String::from("25525511135");
    println!("{:?}", restore_ip_addresses(&s)); 
    let s = String::from("0000");
    println!("{:?}", restore_ip_addresses(&s)); 
    let s = String::from("101023");
    println!("{:?}", restore_ip_addresses(&s)); 
}

fn restore_ip_addresses(s: &String) -> Vec<String> {
    let mut res = Vec::new();
    let mut path = String::new();
    if s.len() < 4 || s.len() > 12 {
        return res;
    }
    dfs_ip(&mut res, &mut path, 0, 0, &s[..]);
    res
}
fn dfs_ip(res: &mut Vec<String>, path: &mut String, u: i32, k: usize, s: &str) {
    if u == 4 {
        if k == s.len() {
            res.push(path.clone());
        }
        return;
    }
    for i in 1..=3 {
        if k + i > s.len() {
            return;
        }
        if is_valid(&s[k..k+i]) {
            path.push_str(&s[k..k+i]);
            if u != 3 {
                path.push('.');
            }
            dfs_ip(res, path, u+1, k+i, s);
            if u != 3 {
                path.pop();
            }
            path.truncate(path.len() - i);
        }
    }
}
fn is_valid(s: &str) -> bool {
    if s.len() > 1 && s.chars().nth(0).unwrap() == '0' {
        return false;
    }
    true
}
fn main() {
    let s = String::from("25525511135");
    println!("{:?}", restore_ip_addresses(&s)); 
    let s = String::from("0000");
    println!("{:?}", restore_ip_addresses(&s)); 
    let s = String::from("101023");
    println!("{:?}", restore_ip_addresses(&s)); 
}