Statistics

Problem Statement for "WordSpaces"

Problem Statement

A spy, working as a reporter at a local newspaper, has been leaking information to enemy countries by hiding messages within the articles. However, he has been found out, and the local intelligence agency wants you to write a program to detect the occurrence of certain words within this newspaper. The difficulty is that the words are not written directly in the articles, but are spaced out by a constant number (possibly zero) of garbage characters. For example, by taking every other character (i.e. the constant number of garbage characters is 1) the word "hello" is encoded in the stream of letters: "haeilelao". Also, the word "the" is encoded in "at bah ate" by starting at the second character and reading every fourth character. Note the number of garbage characters used can be any non-negative integer.

Create a class WordSpaces with a method which takes a String sentence and a String[] words. This method is to determine the first occurrence of each word in words within sentence. Elements of the int[] you return must correspond to words. That is, element i of the int[] corresponds to element i of words. If a word starts at character 0 of the sentence, then that element of the return int[] must be 0. Note that in the sentence: " at bah ate" (same as above, but with a leading space), the word "the" starts at position 2, whereas in the above example without the leading space, the word "the" starts as position 1.

Definition

Class:
WordSpaces
Method:
find
Parameters:
String, String[]
Returns:
int[]
Method signature:
int[] find(String sentence, String[] words)
(be sure your method is public)

Notes

  • In the event that a word does not occur in the sentence with any spacing, use the value -1 for that word.

Constraints

  • sentence will be between 1 and 50 characters in length, inclusive
  • sentence will contain only lowercase letters (a-z) and spaces
  • words will contain between 0 and 50 elements, inclusive
  • each element of words will be between 1 and 50 characters in length, inclusive
  • each element of words will contain only lowercase letters (a-z)

Examples

  1. "zoidal wrote this problem"

    {"ilreh","problem","woe","zar","ot"}

    Returns: { 2, 18, 7, 0, 1 }

  2. "test case number seven"

    {"ts","etc","nees","ten"}

    Returns: { 0, 1, -1, -1 }

  3. "the job of writing testcases is not much fun"

    {"tow","wit","ten","eat"}

    Returns: { -1, 15, 23, -1 }

  4. "sometimes testcases are randomly generated"

    {"set","ate","tea","dome"}

    Returns: { 0, 41, 14, -1 }

  5. "xtywzoapbicndkefflgahmiijnkgloms"

    {"two","pink","flamingos","are","in","this","sentence"}

    Returns: { 1, 7, 15, -1, 9, -1, -1 }

  6. "abcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefg"

    {"gfedcba","acegbdfacegbdfacegbdfaceg","bfcgdaebfcgd","fdbgecafd","cdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefg","dgcfbeadgcfbeadg","ebfcgdaebfcg"}

    Returns: { 6, 0, 1, 5, 2, 3, 4 }

  7. "only four more testcases to go"

    {"yu","ot","cs","x","n","m"}

    Returns: { 3, 0, 19, -1, 1, 10 }

  8. "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx"

    {"aa","bb","cc","dd","ee","ff","gg","hh","ii","jj","kk","ll","mm","nn","oo","pp","qq","rr","ss","tt","uu","vv","ww","xx","yy","zz","aw","kj","oi","ew","sr","ew","zs","en","bq","zy","kw","lw","ox","asd","rew","oiu","the","hak","ewj","sid","jwe","sjd"}

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, -1, -1, 0, 10, 14, 4, 18, 4, 25, 4, 1, -1, 10, 11, 14, -1, -1, -1, -1, -1, -1, -1, -1, -1 }

  9. "the square root of pi is irrational"

    {"pii","tesur","oo","qaer","ooo","pit","pir","qeof"}

    Returns: { 19, 0, 12, 5, -1, -1, -1, 5 }

  10. " too many spaces "

    {"tms","tmp","tma","tmc","tme","tas","tap","taa","tac","tns","one"}

    Returns: { -1, 7, -1, -1, -1, -1, -1, -1, 7, 7, 8 }

  11. "at bah ate"

    {"the","aa","hae"}

    Returns: { 1, 0, 5 }

    By taking the 2nd, 6th, and 10th characters (at positions 1, 5, and 9), we get "the". Thus, the first element of the return value is 1. (garbage spacing is 3) The word "aa" occurs at a number of locations: By taking characters at positions 0 and 4, we get "aa". (garbage spacing is 3) However, we also get "aa" by taking the letters at positions 4 and 7. (garbage spacing is 2) You are to return the position of the first occurrence, so the second element of the return value is 0. "hae" is found by taking letters at positions 5, 7, and 9, so the third element of the return value is 5. (garbage spacing is 1)

  12. "test this one out"

    {"test","tst","hoe","not"}

    Returns: { 0, 0, -1, -1 }

  13. "t ah mi as this"

    {"this","mat","zebra","hh"}

    Returns: { 0, 5, -1, 3 }

  14. "abcdefghijklmnoqrstuvwxyz zywvutsrponmlkjighfedcba"

    {"foy","foz","fox","ace","rom"}

    Returns: { 5, -1, -1, 0, 33 }

  15. "ridikulus ridiculous"

    {"kuri","ks","cs","z","i","rsl"}

    Returns: { 4, 4, 14, -1, 1, 0 }

  16. "a"

    { "a" }

    Returns: { 0 }

  17. "abcdefghijklmnoqrstuvwxyz zywvutsrponmlkjighfedcba"

    { "foy", "foz", "fox", "ace", "rom" }

    Returns: { 5, -1, -1, 0, 33 }

  18. "tdhebtuhgfe bugthe frthe etth th ss hh ther ttther"

    { "the", "ther", "bug", "e", "er", "ug", "bg", "tt", "tr" }

    Returns: { 15, 39, 4, 3, 3, 6, 4, 0, 0 }

  19. "abcdef"

    { "bb" }

    Returns: { -1 }

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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: