比如,str = “ayxbx”,
有以下4种切法 : a | yxbx、ay | xbx、ayx | bx、ayxb | x,
其中第1、3、4种切法符合:x和y的个数,至少在左右两块中的一块里有相同的数量,
所以返回3。
给定一个字符串str,长度为N,
你有N-1种划分方法,把str切成左右两半,返回有几种切法满足:
x和y的个数,至少在左右两块中的一块里有相同的数量。
遍历统计x和y的个数。再次遍历做判断。
时间复杂度:O(N)。
代码用rust编写。代码如下:
fn main() {
let answer = split_same_number_ways("ayxbx");
println!("answer = {}", answer);
}
fn split_same_number_ways(str: &str) -> isize {
if str.len() == 0 {
return 0;
}
let mut x_all: isize = 0;
let mut y_all: isize = 0;
for c in str.chars() {
x_all += if c == 'x' { 1 } else { 0 };
y_all += if c == 'y' { 1 } else { 0 };
}
let mut left_x: isize = if str.chars().nth(0).unwrap() == 'x' {
1
} else {
0
};
let mut left_y: isize = if str.chars().nth(0).unwrap() == 'y' {
1
} else {
0
};
let mut ans: isize = 0;
for i in 1..str.len() {
if left_x == left_y || (x_all - left_x) == (y_all - left_y) {
ans += 1;
}
left_x += if str.chars().nth(i as usize).unwrap() == 'x' {
1
} else {
0
};
left_y += if str.chars().nth(i as usize).unwrap() == 'y' {
1
} else {
0
};
}
return ans;
}
执行结果如下: