yukicoder No.69 - 文字を自由に並び替え

Source

ニコニコミュニティ
問題文

問題概要

アルファベット小文字のみからなる $2$ つの文字列 $A,B$ が与えられる．
文字列 $A$ の文字を自由に並び替えることによって，文字列 $A$ と $B$ を一致させることができるかどうかを判定する問題．

解法

両者の文字列を，文字の列と思ってソートして一致するか調べれば良い．
時間計算量 $O(|A| \log |A|)$．
または，各文字ごとに，それぞれの文字列に何個含まれているかをカウントし，全ての文字に対して，含まれているその文字の数が等しいかどうかを調べれば良い．
この方法だと，時間計算量 $O(|A| + C)$，ここで $C=26$ は文字の種類数．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

int main(){
  string A, B;

  cin >> A >> B;
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());
  if(A==B) puts("YES"); else puts("NO");

  return 0;
}

Current time: 2024年04月19日13時36分05秒
Last modified: 2014年12月23日23時15分54秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：