Statistics

Problem Statement for "WordConnect"

Problem Statement

You are given a table of characters. Words are found in table by taking steps up, down, left, or right (up and down refer to row changes, while left and right refer to column changes). The string of letters stepped on during this process is said to be found. If word is found in table, then all of the positions stepped on while finding word are considered pairwise connected. Each occurrence of word that is found is dealt with separately. Connectivity is transitive: if position x connects to y, and position y connects to z, then positions x and z are connected. Return the number of distinct connected components in table (a connected component is a maximal collection of pairwise connected positions). To simplify matters, the characters in word will be distinct.

Definition

Class:
WordConnect
Method:
numComponents
Parameters:
String, String[]
Returns:
int
Method signature:
int numComponents(String word, String[] table)
(be sure your method is public)

Constraints

  • word will contain between 1 and 26 lowercase letters ('a'-'z'), inclusive.
  • Each character in word will be distinct.
  • table will contain between 1 and 50 elements, inclusive.
  • Each element of table will contain between 1 and 50 characters, inclusive.
  • Each character in table will be a lowercase letter ('a'-'z').
  • Each element of table will contain the same number of letters.

Examples

  1. "top"

    { "toptoptop", "toptoptop" }

    Returns: 6

    There are 6 separate components. Each is numbered below: 111222333 444555666

  2. "top"

    { "aaaaaaaaaaa", "aaaopopoaaa", "aaatototaaa", "aaaopopoaaa", "aaaaaaaaaaa" }

    Returns: 41

    Here there is one large central component, and a surrounding sea of single character components.

  3. "topcader"

    { "topcader", "oaaaaaae", "paaaaaad", "caaaaaaa", "aaaaaaac", "daaaaaap", "eaaaaaao", "redacpot" }

    Returns: 37

    A single component lines the outer edge, surrounding a sea of single character components.

  4. "topcader"

    { "topcoder", "oaaaaaae", "paaaaaad", "caaaaaaa", "aaaaaaac", "daaaaaap", "eaaaaaao", "redocpot" }

    Returns: 50

  5. "a"

    { "aaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaa" }

    Returns: 220

  6. "ab"

    { "ababababababababababababababababab", "ababababababababababababababababab", "ababababababababababababababababab", "ababababababababababababababababab", "ababababababababababababababababab", "ababababababababababababababababab", "ababababababababababababababababab", "ababababababababababababababababab", "ababababababababababababababababab", "ababababababababababababababababab", "ababababababababababababababababab", "ababababababababababababababababab" }

    Returns: 12

  7. "ab"

    { "abababababababababababababababababababab", "babababababababababababababababababababa", "abababababababababababababababababababab", "babababababababababababababababababababa", "abababababababababababababababababababab", "babababababababababababababababababababa", "abababababababababababababababababababab", "babababababababababababababababababababa", "abababababababababababababababababababab", "babababababababababababababababababababa", "abababababababababababababababababababab", "babababababababababababababababababababa", "abababababababababababababababababababab", "babababababababababababababababababababa" }

    Returns: 1

  8. "ab"

    { "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa" }

    Returns: 1

  9. "ab"

    { "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab", "bababababababababababababababababababababababababa", "ababababababababababababababababababababababababab", "ababababababababababababababababababababababababab" }

    Returns: 48

  10. "abcdefghijklmnopqrstuvwxyz"

    { "ab", "dc", "ef", "hg", "ij", "lk", "mn", "po", "qr", "ts", "uv", "xw", "yz", "xy"}

    Returns: 3

  11. "abcdefghijklmnopqrstuvwxyz"

    {"abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "bcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxy", "cdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz", "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyza", "efghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzab", "fghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc", "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd", "hijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcde", "ijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" }

    Returns: 23

  12. "abcdefg"

    { "abcdefg", "babadef", "cbabcde", "dababcd", "edcbabc", "fedcbab", "gfedcba" }

    Returns: 1

  13. "abcdef"

    { "abcdefg", "babadef", "cbabcde", "dababcd", "edcbabc", "fedcbab", "gfedcba" }

    Returns: 3

  14. "abcdefgh"

    { "abcdefg", "babadef", "cbabcde", "dababcd", "edcbabc", "fedcbab", "gfedcba" }

    Returns: 49

  15. "abcdef"

    { "abcdefgfedcba", "abcdefgfedcba", "abcdefgfedcba", "abcdefgfedcba", "abcdefgfedcba", "abcdefgfedcba", "abcdefgfedcba", "abcdefgfedcba" }

    Returns: 24

  16. "abcdefg"

    { "abcdefgfedcba", "abcdefgfedcba", "abcdefgfedcba", "abcdefgfedcba", "abcdefgfedcba", "abcdefgfedcba", "abcdefgfedcba", "abcdefgfedcba" }

    Returns: 8

  17. "abcdefg"

    { "abcdefg", "bcaaaaa", "cdeaaaa", "dafgaaa", "eaafeaa", "faaadca", "gaaaaba" }

    Returns: 25

  18. "abcd"

    { "abcdabcd", "beecbeec", "ceebceeb", "dcbadeea" }

    Returns: 11

  19. "abcde"

    { "abcdeabcde", "bfffdbfffd", "cfffccfffc", "dfffbdfffb", "edcbaedcba" }

    Returns: 20

  20. "abcd"

    { "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "cxxbxdcbabcxxbxdcbabcxxbxdcbabcxxbxdcbabcxxbxdcbab", "dcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxx", "xbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcd", "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "xxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbax", "dcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxx", "xbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcd", "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "xxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbax", "dcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxx", "xbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcd", "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "xxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbax", "dcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxx", "xbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcd", "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "xxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbax", "dcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxx", "xbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcd", "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "xxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbax", "dcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxx", "xbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcd", "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "xxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbax", "dcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxx", "xbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcd", "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "xxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbax", "dcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxx", "xbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcd", "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "xxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbax", "dcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxx", "xbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcd", "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "xxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbax", "dcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxx", "xbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcd", "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "xxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbax", "dcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxx", "xbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcdxbxxxxabcd", "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "xxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbax", "dcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxxdcbaxxbxxx", "xbxxcbabcdxbxxcbabcdxbxxcbabcdxbxxcbabcdxbxxcbabcd", "xabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbxxabcdxxxbx", "xxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbaxxxxbxdcbax"}

    Returns: 1243

  21. "abcdefghijklmnopqrstuvwxyz"

    {"abcdefghijklmnopqrstuvwxyz", "bcdefghijklmnopqrstuvwxyzy", "cdefghijklmnopqrstuvwxyzyx", "defghijklmnopqrstuvwxyzyxw", "efghijklmnopqrstuvwxyzyxwv", "fghijklmnopqrstuvwxyzyxwvu", "ghijklmnopqrstuvwxyzyxwvut", "hijklmnopqrstuvwxyzyxwvuts", "ijklmnopqrstuvwxyzyxwvutsr", "jklmnopqrstuvwxyzyxwvutsrq", "klmnopqrstuvwxyzyxwvutsrqp", "lmnopqrstuvwxyzyxwvutsrqpo", "mnopqrstuvwxyzyxwvutsrqpon", "nopqrstuvwxyzyxwvutsrqponm", "opqrstuvwxyzyxwvutsrqponml", "pqrstuvwxyzyxwvutsrqponmlk", "qrstuvwxyzyxwvutsrqponmlkj", "rstuvwxyzyxwvutsrqponmlkji", "stuvwxyzyxwvutsrqponmlkjih", "tuvwxyzyxwvutsrqponmlkjihg", "uvwxyzyxwvutsrqponmlkjihgf", "vwxyzyxwvutsrqponmlkjihgfe", "wxyzyxwvutsrqponmlkjihgfed", "xyzyxwvutsrqponmlkjihgfedc", "yzyxwvutsrqponmlkjihgfedcb", "zyxwvutsrqponmlkjihgfedcba" }

    Returns: 1

  22. "abcdefghijklmnopqrstuvwxyz"

    {"abcdefghijklmnopqrstuvwxyz", "bcdefghijklmnopqrstuvwxyza", "cdefghijklmnopqrstuvwxyzab", "defghijklmnopqrstuvwxyzabc", "efghijklmnopqrstuvwxyzabcd", "fghijklmnopqrstuvwxyzabcde", "ghijklmnopqrstuvwxyzabcdef", "hijklmnopqrstuvwxyzabcdefg", "ijklmnopqrstuvwxyzabcedfgh", "jklmnopqrstuvwxyzabcdefghi", "klmnopqrstuvwxyzabcdefghij", "lmnopqrstuvwxyzabcdefghijk", "mnopqrstuvwxyzabcdefghijkl", "nopqrstuvwxyzabcdefghijklm", "opqrstuvwxyzabcdefghijklmn", "pqrstuvwxyzabcdefghijklmno", "qrstuvwxyzabcdefghijklmnop", "rstuvwxyzabcdefghijklmnopq", "stuvwxyzabcdefghijklmnopqr", "tuvwxyzabcdefghijklmnopqrs", "uvwxyzabcdefghijklmnopqrst", "vwxyzabcdefghijklmnopqrstu", "wxyzabcdefghijklmnopqrstuv", "xyzabcdefghijklmnopqrstuvw", "yzabcdefghijklmnopqrstuvwx", "zabcdefghijklmnopqrstuvwxy" }

    Returns: 326

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: