Advertisement
HjHimansh

Untitled

Oct 24th, 2023
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.50 KB | None | 0 0
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <bits/stdc++.h>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9.  
  10. vector<string> strs;
  11.  
  12. struct returnType{
  13. int length;
  14. char first;
  15. char last;
  16.  
  17. bool operator==(const returnType& other) const {
  18. return length == other.length && first == other.first && last == other.last;
  19. }
  20.  
  21. };
  22.  
  23. typedef struct returnType returnType;
  24.  
  25. struct returnTypeHash {
  26. std::size_t operator()(const returnType& rt) const {
  27. std::size_t hash = 17;
  28. hash = hash * 31 + std::hash<int>{}(rt.length);
  29. hash = hash * 31 + std::hash<char>{}(rt.first);
  30. hash = hash * 31 + std::hash<char>{}(rt.last);
  31. return hash;
  32. }
  33. };
  34.  
  35. // returns total possiblities possible after operating on str[i] and possible str[i-1]s...
  36. unordered_set<returnType, returnTypeHash> solve(int i){
  37. unordered_set<returnType, returnTypeHash> toReturn;
  38. // cout << i << endl;
  39.  
  40. returnType curr;
  41. curr.length = strs[i].size();
  42. curr.first = strs[i][0];
  43. curr.last = strs[i][strs[i].size()-1];
  44.  
  45. if(i==0) {
  46. toReturn.insert(curr);
  47. return toReturn;
  48. }
  49. unordered_set<returnType, returnTypeHash> possibleStrPrevious = solve(i-1);
  50. // cout << i << " -- Hey there" << possibleStrPrevious.size() << endl;
  51. for(auto &x: possibleStrPrevious) {
  52. returnType temp1, temp2;
  53. temp1.first = x.first;
  54. temp1.last = curr.last;
  55. if(x.last == curr.first) {
  56. temp1.length = x.length + curr.length - 1;
  57. }
  58. else {
  59. temp1.length = x.length + curr.length;
  60. }
  61.  
  62. temp2.first = curr.first;
  63. temp2.last = x.last;
  64. if(curr.last == x.first) {
  65. temp2.length = curr.length + x.length - 1;
  66. }
  67. else {
  68. temp2.length = curr.length + x.length;
  69. }
  70.  
  71. toReturn.insert(temp1);
  72. toReturn.insert(temp2);
  73. }
  74.  
  75. return toReturn;
  76. }
  77.  
  78.  
  79. int main() {
  80. int n; cin >> n;
  81.  
  82. while(n--) {
  83. string temp; cin >> temp;
  84. strs.push_back(temp);
  85. }
  86.  
  87. n = strs.size();
  88.  
  89. unordered_set<returnType, returnTypeHash> possiblities = solve(n-1);
  90. int answer = INT_MAX;
  91. // cout << "Length = " << possiblities.size() << endl;
  92. for(auto &x: possiblities) {
  93. answer = min(answer, x.length);
  94. }
  95.  
  96. cout << answer << endl;
  97.  
  98. return 0;
  99. }
  100.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement