LeetCode Biweekly Contest 13 3問目 - Synonymous Sentences [1258]

Source

LeetCode Biweekly Contest 13
問題文

問題概要

省略

解法

省略

cLay（version 20191123-1）のコード

C++に変換後のコードはこちら

#define main dummy_main
{}
#undef main

map<string, int> mp;
string lis[10][20];
int tot, sz[10];
vector<string> res, in, tmp;

void solve(int dep){
  int k;
  if(dep==in.size()) res.push_back( Implode(tmp, " ") ), return;
  if(mp.count(in[dep])==0) solve(dep+1), return;
  k = mp[in[dep]];
  rep(i,sz[k]) tmp[dep] = lis[k][i], solve(dep+1);
}

class Solution {
public:
  vector<string> generateSentences(vector<vector<string>>& S, string text) {
    mp.clear();
    tot = 0;
    rep(i,10) sz[i] = 0;

    rep(i,S.size()){
      if(mp.count(S[i][0])) continue;
      lis[tot][sz[tot]++] = S[i][0]; mp[S[i][0]] = tot;
      lis[tot][sz[tot]++] = S[i][1]; mp[S[i][1]] = tot;
      rep(j,i+1,S.size()){
        if(mp.count(S[j][0]) && mp.count(S[j][1])) continue;
        if(mp.count(S[j][0])) lis[tot][sz[tot]++] = S[j][1], mp[S[j][1]] = tot, continue;
        if(mp.count(S[j][1])) lis[tot][sz[tot]++] = S[j][0], mp[S[j][0]] = tot, continue;
      }
      tot++;
    }

    res.clear();
    tmp = in = Explode(text, " ");
    solve(0);
    sort(res.begin(), res.end());
    return res;
  }
};

Current time: 2024年04月26日00時21分15秒
Last modified: 2019年11月23日18時30分06秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)