Question on combining words

It is resolved thankyou everyone for the great help
Last edited on
You need a special comparison function that will test to see if the end of a word is found at the beginning of another.

    x 1 0 <- index
j i m m y

 index ->  0 1 x
           m y o l i t a

(two character match)

You can use the STL to do it with reverse iterators:

1
2
3
4
5
6
7
8
9
10
11
12
13
std::string frags( const std::string& a, const std::string& b )
{
  auto mm = mismatch( a.rbegin(), a.rbegin() + std::min( a.length(), b.length() ), b.begin() );
  auto mlen = std::distance( b.begin(), mm.second );
  if (mlen > N)
  {
    return a + b.substr( mlen );
  }
  else 
  {
    return "no match";
  }
}

Something like that?

Hope this helps.
interesting, but I am trying to avoid using any C. It's too "hardcore" for me right now. Maybe in a few years. Also the list doesn't have to be a size of 2. It can be size of N and I need to append it over and over if there's a special comparison. Better if you could represent your answer in psuedo code.
Last edited on
Ok, now I created my own solution. It does passes the test and gives me

1
2
3
4
5
6
7
['jimmy', 'myolita']
jimmyolita
['jimmy', 'myolita', 'jimmyolita']
   
['myolita', 'jimmy']
jimmyolita
['myolita', 'jimmy', 'jimmyolita']


However, I am really not liking the fact that I am using check and maxNum. Do you have any idea to further improve my algorithm?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def frags(strings):
    check = 1
    maxNum = 1

    for x in range(0,len(strings)):
        for y in range(0,len(strings)):
            if x != y:                
                for i in range(0,len(strings[y])):
                    if strings[x].find(strings[y][:i]) > maxNum:
                        check = 0
                        maxNum = strings[x].find(strings[y][:i])
                        
                if check == 0:
                   toReturn = strings[x][:maxNum] + strings[y]
                   strings.append(toReturn)
                   check = 1
                   maxNum = 1
    return toReturn
Ah, sorry. You did say you were sticking to Python.

You are doing way too much there. The check and maxNum exist to limit the answers you are getting.

The algorithm I gave you checks exactly two strings against each other (non-commutative). Find the number of characters that match in two strings:
- from the last to the first in string a
- from the first to the last in string b
If n >= N then you have a match.

The outer algorithm, then, needs to loop through the strings to find all valid combinations of matches > N. For each valid match, generate the result and add it to your list of results.

You will get further if you try to write it as two separate functions.

Hope this helps.
Registered users can post here. Sign in or register to post.