Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <bits/stdc++.h>
- #include <algorithm>
- using namespace std;
- vector<string> strs;
- struct returnType{
- int length;
- char first;
- char last;
- bool operator==(const returnType& other) const {
- return length == other.length && first == other.first && last == other.last;
- }
- };
- typedef struct returnType returnType;
- struct returnTypeHash {
- std::size_t operator()(const returnType& rt) const {
- std::size_t hash = 17;
- hash = hash * 31 + std::hash<int>{}(rt.length);
- hash = hash * 31 + std::hash<char>{}(rt.first);
- hash = hash * 31 + std::hash<char>{}(rt.last);
- return hash;
- }
- };
- // returns total possiblities possible after operating on str[i] and possible str[i-1]s...
- unordered_set<returnType, returnTypeHash> solve(int i){
- unordered_set<returnType, returnTypeHash> toReturn;
- // cout << i << endl;
- returnType curr;
- curr.length = strs[i].size();
- curr.first = strs[i][0];
- curr.last = strs[i][strs[i].size()-1];
- if(i==0) {
- toReturn.insert(curr);
- return toReturn;
- }
- unordered_set<returnType, returnTypeHash> possibleStrPrevious = solve(i-1);
- // cout << i << " -- Hey there" << possibleStrPrevious.size() << endl;
- for(auto &x: possibleStrPrevious) {
- returnType temp1, temp2;
- temp1.first = x.first;
- temp1.last = curr.last;
- if(x.last == curr.first) {
- temp1.length = x.length + curr.length - 1;
- }
- else {
- temp1.length = x.length + curr.length;
- }
- temp2.first = curr.first;
- temp2.last = x.last;
- if(curr.last == x.first) {
- temp2.length = curr.length + x.length - 1;
- }
- else {
- temp2.length = curr.length + x.length;
- }
- toReturn.insert(temp1);
- toReturn.insert(temp2);
- }
- return toReturn;
- }
- int main() {
- int n; cin >> n;
- while(n--) {
- string temp; cin >> temp;
- strs.push_back(temp);
- }
- n = strs.size();
- unordered_set<returnType, returnTypeHash> possiblities = solve(n-1);
- int answer = INT_MAX;
- // cout << "Length = " << possiblities.size() << endl;
- for(auto &x: possiblities) {
- answer = min(answer, x.length);
- }
- cout << answer << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement