第JavaC++題解leetcode判定是否為字符重排目錄題目要求思路一：排序JavaC++Rust思路二：詞頻統(tǒng)計JavaC++Rust總結(jié)

題目要求

思路一：排序

Java

classSolution{

publicbooleanCheckPermutation(Strings1,Strings2){

if(s1.length()!=s2.length())

returnfalse;

char[]sort1=s1.toCharArray();

Arrays.sort(sort1);

char[]sort2=s2.toCharArray();

Arrays.sort(sort2);

returnArrays.equals(sort1,sort2);

時間復(fù)雜度：O(nlogn)，排序復(fù)雜度空間復(fù)雜度：O(n)，拷貝字符串用于排序

C++

classSolution{

public:

boolCheckPermutation(strings1,strings2){

if(s1.size()!=s2.size())

returnfalse;

sort(s1.begin(),s1.end());

sort(s2.begin(),s2.end());

returns1==s2;

時間復(fù)雜度：O(nlog?n)O(n\logn)O(nlogn)，排序復(fù)雜度空間復(fù)雜度：O(log?n)O(\logn)O(logn)，排序需要

Rust

implSolution{

pubfncheck_permutation(s1:String,s2:String)-bool{

ifs1.len()!=s2.len(){

false

else{

let(mutsort1,mutsort2)=(s1.as_bytes().to_vec(),s2.as_bytes().to_vec());

sort1.sort();

sort2.sort();

sort1==sort2

時間復(fù)雜度：O(nlog?n)，排序復(fù)雜度空間復(fù)雜度：O(n)，拷貝字符串用于排序

思路二：詞頻統(tǒng)計

classSolution{

publicbooleanCheckPermutation(Strings1,Strings2){

if(s1.length()!=s2.length())

returnfalse;

int[]freq=newint[128];

intdiff=0;

for(inti=0;is1.length();i++){

if(++freq[s1.charAt(i)]==1)

diff++;

if(--freq[s2.charAt(i)]==0)

diff--;

returndiff==0;

時間復(fù)雜度：O(n)空間復(fù)雜度：O(C)，常數(shù)C為字符集大小

classSolution{

public:

boolCheckPermutation(strings1,strings2){

if(s1.size()!=s2.size())

returnfalse;

intfreq[128];

memset(freq,0,sizeof(freq));

intdiff=0;

for(inti=0;is1.size();i++){

if(++freq[s1[i]]==1)

diff++;

if(--freq[s2[i]]==0)

diff--;

returndiff==0;

時間復(fù)雜度：O(n)空間復(fù)雜度：O(C)，常數(shù)C為字符集大小

implSolution{

pubfncheck_permutation(s1:String,s2:String)-bool{

s1.len()==s2.len()s1.bytes().zip(s2.bytes()).fold(vec![0;128],|mutfreq,(c1,c2)|{

freq[c1asusize]+=1;

freq[c2asusize]-=1;

freq

}).into_iter().all(|diff|diff==0)

時間復(fù)雜度：O(n)空間復(fù)雜度：O(C)，常數(shù)C為字符集大小

總結(jié)

簡單模擬