forked from keshavnandan/Topcoder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathLostCharacter.html
23 lines (19 loc) · 5.59 KB
/
LostCharacter.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>In this problem we are dealing with strings of lowercase English letters.
When comparing our strings, we are using the standard lexicographic order.
For example, "cat" < "do" < "dog" < "done".
(See Notes for a formal definition.)<br></br><br></br>
Suppose that L is a list of strings and that S is one of those strings.
The <i>position</i> of S in L is the 0-based index of the first occurrence of S after L is sorted lexicographically.
(Equivalently, the position of S in L can be defined as the number of strings in L that are strictly smaller than S.)<br></br><br></br>
For example, for the list L = {"abc", "bcd", "cde", "cdf", "bbc"}, the corresponding positions would be {0, 2, 3, 4, 1}.
For the list L = {"a", "a", "b", "b", "c", "c"} the positions would be {0, 0, 2, 2, 4, 4}.<br></br><br></br>
Wolf Sothe has found an old list of strings.
Some characters in the list were damaged beyond recognition.
You are given the list as a vector <string> <b>str</b>.
In <b>str</b>, the damaged characters are represented by the character '?' (question mark).<br></br><br></br>
Return a vector <int> with as many elements as <b>str</b>.
For each valid i, the i-th element of the return value should be the smallest possible position of the i-th element of Sothe's list.</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>LostCharacter</td></tr><tr><td>Method:</td><td>getmins</td></tr><tr><td>Parameters:</td><td>vector <string></td></tr><tr><td>Returns:</td><td>vector <int></td></tr><tr><td>Method signature:</td><td>vector <int> getmins(vector <string> str)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td colspan="2"><h3>Limits</h3></td></tr><tr><td>    </td><td><table><tr><td>Time limit (s):</td><td>2.000</td></tr><tr><td>Memory limit (MB):</td><td>256</td></tr><tr><td>Stack limit (MB):</td><td>256</td></tr></table></td></tr><tr><td colspan="2"><h3>Notes</h3></td></tr><tr><td align="center" valign="top">-</td><td>Given two strings A and B, we say that A is smaller than B if either A is a proper prefix of B, or there is a non-negative integer i such that A[i]<B[i] and for all j<i we have A[j]=B[j].</td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>str</b> will contain between 1 and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element in <b>str</b> will contain between 1 and 50 characters, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each character in <b>str</b> will be either a lowercase English letter ('a'-'z'), or '?'.</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"abc","bcd","cde","cdf","bbc"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: {0, 2, 3, 4, 1 }</pre></td></tr><tr><td><table><tr><td colspan="2">This is the first example from the problem statement.
As there are no damaged letters, there is only one possible lexicographical order and you should return the corresponding positions.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"?ala","ara","baba"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: {0, 0, 1 }</pre></td></tr><tr><td><table><tr><td colspan="2">In this test case we have one damaged character.
If the damaged character was an 'a', the positions were {0,1,2}.
Otherwise, the positions were {2,0,1}.
Hence, the smallest possible position of "?ala" is 0, the smallest possible position of "ara" is 0, and the smallest possible position of "baba" is 1.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"a?","a","a","ab","aa"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: {2, 0, 0, 3, 2 }</pre></td></tr><tr><td><table><tr><td colspan="2">Sothe's list may contain duplicates.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"s?nu?ke","sm??eke","?sna?ke","so?th?e","shake??"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: {0, 1, 0, 2, 0 }</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">4)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"?","z?","zz?","zzz?","zzzz?","zzzzz?","zzzzzz?"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: {0, 1, 2, 3, 4, 5, 6 }</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr></table><p>This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. </p></body></html>