Databases
StackOverflow2013
Postsdbo
POWord lexical families
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWord lexical families
    primarykey
    data
    text
    <p>I am given a set of N words, and an integer K. 2 words are in the same group if they have exactly the first k letters and the last k letters identical. If they have more than k letters identical or less than k letters identical then the words are not in the same group. For example: For k=3.</p> <p>"abcdefg" and "abczefg" are in the same group<br> "abcddefg" and "abcdzefg" are not in the same group (the first k+1 letters are identical)<br> "abc" and "abc" are in the same group<br></p> <p>A word can be in more than 1 groups. For example (k=3):<br> "abczefg" and "abcefg" form a group<br> "abczaefg" and "abcefg" form a group<br> "abczaefg" and "abczefg" are not in the same group (the first k+1 letters are identical)</p> <p>The problem asks me to find the number of groups which contain the maximum number of words.</p> <p>I thought about using a Trie (or Prefix Tree) and I assume this is the right data structure for this problem but I don't know how can I adapt them for this problem, because the part where if 2 words have more than k letters identical are not in the same group confuse me. My ideea has the complexity O(N*N*K) and considering that N&lt;=10,000 and K&lt;=100 I don't think that this ideea is fast enough. I would like to explain you my ideea, but it is not cleary yet even for me and I don't even know if it is correct, so I will skip this part.</p> <p>My question is if there is a way I could solve this problem using a faster algorithm, and if there is such algorithm, I kindly ask you to explain it a little bit. Thank you in advance and I am sorry for the gramatical mistakes and if I didn't explain the problem clearly!</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMike
    1. USaltair1000
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWord lexical families
      1. USa.u.r
      1. VTFavorite
    2. VO
      singulars
      1. POWord lexical families
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload