Editorial - CHDIR

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Hanzala Sohrab
Tester: Anjani Kumar

DIFFICULTY:

EASY-MEDIUM.

PREREQUISITES:

Strings, Implementation

PROBLEM:

Find if a string is present in a list of strings. If present, find the length of the shortest prefix of the queried string that cannot be found in any other string.

EXPLANATION:

Store the given strings in a map. If the queried string is not present in the map, print -1. Otherwise, print the length of the shortest prefix of the queried string that cannot be found in any other string.

Suppose, N = 3, the strings are \{documents, downloads, docs\}, and the queried string is documents.

  • The prefix d is present in all the three strings - \{documents, downloads,docs\}.
  • The prefix do is also present in all the three strings - \{documents, downloads,docs\}.
  • The prefix doc is present in two strings - \{documents, docs\}.
  • The prefix docu is present in only one string - \{documents\}.

So, the length of the shortest prefix docu is 4.
Therefore, in the command line, Chef has to type cd docu before finally pressing the Tab key. So, in total Chef has to print 7 keys - \{c, d, space, d, o, c, u\} apart from the Tab key. So the answer is 7.

NOTE: Suppose N=1 and the only string is \{documents\} and the queried string is documents, then Chef only has to type cd before pressing Tab key because there is only one string and that matches with the queried string. So, Chef has to type in these characters - \{c, d, space\}. So, in this case the answer is 3.

NOTE: This problem can also be solved using tries or ternary trees. Within the given constraints, a normal solution would suffice. However, the reader is requested to try out the implementation using tries.

COMPLEXITY:

Using iterative brute-force method - O(N*M), where N is the number of strings and M is the length of the queried string.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while (t--)
    {
        int i, j, n;
        cin >> n;
        unordered_map<string, bool> m;
        string x, s;
        vector<string> v(n);
        for (i = 0; i < n; ++i)
        {
            cin >> x;
            if (m.find(x) == m.end())
                m.insert(make_pair(x, true));
            v[i] = x;
        }
        cin >> s;
        if (m.find(s) == m.end())
        {
            cout << "-1\n";
            continue;
        }
        int M = 0;
        for (i = 0; i < n; ++i)
        {
            for (j = 0; j < min(s.size(), v[i].size()); ++j)
                if (s == v[i])
                    break;
                else if (s[j] != v[i][j])
                    break;
            // cout << "\n" << v[i] << ' ' << j;
            M = max(M, j+1);
            if (!j and n == 1)
                M = 0;
        }
        cout << M + 3 << '\n';
    }
    return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    if(n == 0) {
        cout << "-1\n";
        return;
    }
    if(n == 1) {
        cout << "3\n";
        return;
    }
    unordered_set<string> _set;
    string A[n];
    for(int i = 0; i < n; i++) {
        cin >> A[i];
        _set.insert(A[i]);
    }
    string ch;
    cin >> ch;
 
    if(_set.find(ch) == _set.end()) {
        cout << "-1\n";
        return;
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        int j;
        int L = min(ch.size(), A[i].size());
        for(j = 0; j < L;j++) {
            if(ch == A[i]) break;
            if(ch[j] != A[i][j]) break; 
        }
        ans = max(ans, j);
    }
    cout << ans + 4 << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}