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: 2017年09月22日22時28分39秒
Last modified: 2014年12月23日23時15分54秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: