Algorithm: Is it possible to form a valid string The Next CEO of Stack OverflowHow to check if a string contains a substring in BashWhat is the best algorithm for an overridden System.Object.GetHashCode?How to check whether a string contains a substring in JavaScript?How do I check if a string contains another string in Objective-C?Does Python have a string 'contains' substring method?How to implement substring algorithmHow do I check if a string contains a specific word?Computing All The Possible Substrings of a Given StringImage Processing: Algorithm Improvement for 'Coca-Cola Can' RecognitionWhat is the optimal algorithm for the game 2048?
How do scammers retract money, while you can’t?
How to safely derail a train during transit?
When airplanes disconnect from a tanker during air to air refueling, why do they bank so sharply to the right?
Trouble understanding the speech of overseas colleagues
Too much space between section and text in a twocolumn document
Inappropriate reference requests from Journal reviewers
If the heap is initialized for security, then why is the stack uninitialized?
Return the Closest Prime Number
How to Reset Passwords on Multiple Websites Easily?
Describing a person. What needs to be mentioned?
Science fiction (dystopian) short story set after WWIII
How to start emacs in "nothing" mode (`fundamental-mode`)
What do "high sea" and "carry" mean in this sentence?
How to use tikz in fbox?
How should I support this large drywall patch?
Why does C# sound extremely flat when saxophone is tuned to G?
How can I quit an app using Terminal?
How do I get the green key off the shelf in the Dobby level of Lego Harry Potter 2?
Horror movie/show or scene where a horse creature opens its mouth really wide and devours a man in a stables
Where to find order of arguments for default functions
Would this house-rule that treats advantage as a +1 to the roll instead (and disadvantage as -1) and allows them to stack be balanced?
Grabbing quick drinks
What happens if you roll doubles 3 times then land on "Go to jail?"
Is the concept of a "numerable" fiber bundle really useful or an empty generalization?
Algorithm: Is it possible to form a valid string
The Next CEO of Stack OverflowHow to check if a string contains a substring in BashWhat is the best algorithm for an overridden System.Object.GetHashCode?How to check whether a string contains a substring in JavaScript?How do I check if a string contains another string in Objective-C?Does Python have a string 'contains' substring method?How to implement substring algorithmHow do I check if a string contains a specific word?Computing All The Possible Substrings of a Given StringImage Processing: Algorithm Improvement for 'Coca-Cola Can' RecognitionWhat is the optimal algorithm for the game 2048?
Assume we have n three letter substrings. It is possible to make a string of length n+2 out of these N substrings by concatenating them (Where overlapping letters are written only once) . Whereby this string must have the form a1,a2,a3,a4...
So it is only allowed to link two substrings if they overlap at two adjacent places: 'yxz' + 'xzw' = 'yxzw' , but 'yxz' + 'aby' is for example not allowed.
Example 1: The n = 3 three letter substrings are 'abc','cde','bcd' Output: YES
. Because 'abc' + 'bcd'+ 'cde' = 'abcde' is a valid String with n+2 = 5 letters.
Example 2: The n = 3 three letter substrings are 'abc','bca','bcd' Output: NO. Because its not possible to concatenating them all.
How can i finde an efficient algorithm for this problem? Trying all possible combinations takes far too long with O(n!)
algorithm substring
asked Mar 8 at 12:49
DiefapaDiefapa
112
|
show 1 more comment
Assume we have n three letter substrings. It is possible to make a string of length n+2 out of these N substrings by concatenating them (Where overlapping letters are written only once) . Whereby this string must have the form a1,a2,a3,a4...
So it is only allowed to link two substrings if they overlap at two adjacent places: 'yxz' + 'xzw' = 'yxzw' , but 'yxz' + 'aby' is for example not allowed.
Example 1: The n = 3 three letter substrings are 'abc','cde','bcd' Output: YES
. Because 'abc' + 'bcd'+ 'cde' = 'abcde' is a valid String with n+2 = 5 letters.
Example 2: The n = 3 three letter substrings are 'abc','bca','bcd' Output: NO. Because its not possible to concatenating them all.
How can i finde an efficient algorithm for this problem? Trying all possible combinations takes far too long with O(n!)
algorithm substring
asked Mar 8 at 12:49
DiefapaDiefapa
112
I think you can use 2 maps. How large can benthough?
– vivek_23
Mar 8 at 13:25
@vivek_23 the maximum value of n is approximately in the order of 10^4
– Diefapa
Mar 8 at 13:29
Looks like you will need to use backtracking for this. Because in case of a clash, we can't guarantee which one leads us to a solution consuming all substrings. Also, can a single substring repeat?
– vivek_23
Mar 8 at 13:50
Why doesExample 2have no solution? I seebca+abc=>bcabc, 5 characters from a set of 3 strings. Do we have to use all strings in the set? Must they be used in order?
– Prune
Mar 8 at 19:19
@Prune I was under the impression they must overlap exactly on two characters (end + beginning). Hence the OP's example, 'yxz' + 'xzw' = 'yxzw'
– גלעד ברקן
Mar 8 at 19:37
|
show 1 more comment
Assume we have n three letter substrings. It is possible to make a string of length n+2 out of these N substrings by concatenating them (Where overlapping letters are written only once) . Whereby this string must have the form a1,a2,a3,a4...
So it is only allowed to link two substrings if they overlap at two adjacent places: 'yxz' + 'xzw' = 'yxzw' , but 'yxz' + 'aby' is for example not allowed.
Example 1: The n = 3 three letter substrings are 'abc','cde','bcd' Output: YES
. Because 'abc' + 'bcd'+ 'cde' = 'abcde' is a valid String with n+2 = 5 letters.
Example 2: The n = 3 three letter substrings are 'abc','bca','bcd' Output: NO. Because its not possible to concatenating them all.
How can i finde an efficient algorithm for this problem? Trying all possible combinations takes far too long with O(n!)
algorithm substring
asked Mar 8 at 12:49
DiefapaDiefapa
112
Assume we have n three letter substrings. It is possible to make a string of length n+2 out of these N substrings by concatenating them (Where overlapping letters are written only once) . Whereby this string must have the form a1,a2,a3,a4...
So it is only allowed to link two substrings if they overlap at two adjacent places: 'yxz' + 'xzw' = 'yxzw' , but 'yxz' + 'aby' is for example not allowed.
Example 1: The n = 3 three letter substrings are 'abc','cde','bcd' Output: YES
. Because 'abc' + 'bcd'+ 'cde' = 'abcde' is a valid String with n+2 = 5 letters.
Example 2: The n = 3 three letter substrings are 'abc','bca','bcd' Output: NO. Because its not possible to concatenating them all.
How can i finde an efficient algorithm for this problem? Trying all possible combinations takes far too long with O(n!)
algorithm substring
algorithm substring
asked Mar 8 at 12:49
DiefapaDiefapa
112
asked Mar 8 at 12:49
DiefapaDiefapa
112
asked Mar 8 at 12:49
DiefapaDiefapa
112
asked Mar 8 at 12:49
DiefapaDiefapa
112
asked Mar 8 at 12:49
DiefapaDiefapa
112
112
I think you can use 2 maps. How large can benthough?
– vivek_23
Mar 8 at 13:25
@vivek_23 the maximum value of n is approximately in the order of 10^4
– Diefapa
Mar 8 at 13:29
Looks like you will need to use backtracking for this. Because in case of a clash, we can't guarantee which one leads us to a solution consuming all substrings. Also, can a single substring repeat?
– vivek_23
Mar 8 at 13:50
Why doesExample 2have no solution? I seebca+abc=>bcabc, 5 characters from a set of 3 strings. Do we have to use all strings in the set? Must they be used in order?
– Prune
Mar 8 at 19:19
@Prune I was under the impression they must overlap exactly on two characters (end + beginning). Hence the OP's example, 'yxz' + 'xzw' = 'yxzw'
– גלעד ברקן
Mar 8 at 19:37
|
show 1 more comment
I think you can use 2 maps. How large can benthough?
– vivek_23
Mar 8 at 13:25
@vivek_23 the maximum value of n is approximately in the order of 10^4
– Diefapa
Mar 8 at 13:29
Looks like you will need to use backtracking for this. Because in case of a clash, we can't guarantee which one leads us to a solution consuming all substrings. Also, can a single substring repeat?
– vivek_23
Mar 8 at 13:50
Why doesExample 2have no solution? I seebca+abc=>bcabc, 5 characters from a set of 3 strings. Do we have to use all strings in the set? Must they be used in order?
– Prune
Mar 8 at 19:19
@Prune I was under the impression they must overlap exactly on two characters (end + beginning). Hence the OP's example, 'yxz' + 'xzw' = 'yxzw'
– גלעד ברקן
Mar 8 at 19:37
I think you can use 2 maps. How large can be
n though?– vivek_23
Mar 8 at 13:25
I think you can use 2 maps. How large can be
n though?– vivek_23
Mar 8 at 13:25
@vivek_23 the maximum value of n is approximately in the order of 10^4
– Diefapa
Mar 8 at 13:29
@vivek_23 the maximum value of n is approximately in the order of 10^4
– Diefapa
Mar 8 at 13:29
Looks like you will need to use backtracking for this. Because in case of a clash, we can't guarantee which one leads us to a solution consuming all substrings. Also, can a single substring repeat?
– vivek_23
Mar 8 at 13:50
Looks like you will need to use backtracking for this. Because in case of a clash, we can't guarantee which one leads us to a solution consuming all substrings. Also, can a single substring repeat?
– vivek_23
Mar 8 at 13:50
Why does
Example 2 have no solution? I see bca + abc => bcabc, 5 characters from a set of 3 strings. Do we have to use all strings in the set? Must they be used in order?– Prune
Mar 8 at 19:19
Why does
Example 2 have no solution? I see bca + abc => bcabc, 5 characters from a set of 3 strings. Do we have to use all strings in the set? Must they be used in order?– Prune
Mar 8 at 19:19
@Prune I was under the impression they must overlap exactly on two characters (end + beginning). Hence the OP's example, 'yxz' + 'xzw' = 'yxzw'
– גלעד ברקן
Mar 8 at 19:37
@Prune I was under the impression they must overlap exactly on two characters (end + beginning). Hence the OP's example, 'yxz' + 'xzw' = 'yxzw'
– גלעד ברקן
Mar 8 at 19:37
|
show 1 more comment
1 Answer
1
active
oldest
votes
One of the popular approaches to solving this kind of problems is to build the overlap graph of the input sequences, whose vertices are your triplets and where an arc a_i -> a_j between two triplets means that the last two letters of a_i are the first two letters of a_j; and then to find a Hamiltonian path in the resulting graph.
A naïve search would of course not outperform the exhaustive search you mention, but the linked Wikipedia article gives some leads on how to do this more efficiently.
answered Mar 8 at 13:40
Anthony LabarreAnthony Labarre
1,6822033
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55063593%2falgorithm-is-it-possible-to-form-a-valid-string%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
One of the popular approaches to solving this kind of problems is to build the overlap graph of the input sequences, whose vertices are your triplets and where an arc a_i -> a_j between two triplets means that the last two letters of a_i are the first two letters of a_j; and then to find a Hamiltonian path in the resulting graph.
A naïve search would of course not outperform the exhaustive search you mention, but the linked Wikipedia article gives some leads on how to do this more efficiently.
answered Mar 8 at 13:40
Anthony LabarreAnthony Labarre
1,6822033
add a comment |
One of the popular approaches to solving this kind of problems is to build the overlap graph of the input sequences, whose vertices are your triplets and where an arc a_i -> a_j between two triplets means that the last two letters of a_i are the first two letters of a_j; and then to find a Hamiltonian path in the resulting graph.
A naïve search would of course not outperform the exhaustive search you mention, but the linked Wikipedia article gives some leads on how to do this more efficiently.
answered Mar 8 at 13:40
Anthony LabarreAnthony Labarre
1,6822033
add a comment |
One of the popular approaches to solving this kind of problems is to build the overlap graph of the input sequences, whose vertices are your triplets and where an arc a_i -> a_j between two triplets means that the last two letters of a_i are the first two letters of a_j; and then to find a Hamiltonian path in the resulting graph.
A naïve search would of course not outperform the exhaustive search you mention, but the linked Wikipedia article gives some leads on how to do this more efficiently.
answered Mar 8 at 13:40
Anthony LabarreAnthony Labarre
1,6822033
One of the popular approaches to solving this kind of problems is to build the overlap graph of the input sequences, whose vertices are your triplets and where an arc a_i -> a_j between two triplets means that the last two letters of a_i are the first two letters of a_j; and then to find a Hamiltonian path in the resulting graph.
A naïve search would of course not outperform the exhaustive search you mention, but the linked Wikipedia article gives some leads on how to do this more efficiently.
answered Mar 8 at 13:40
Anthony LabarreAnthony Labarre
1,6822033
answered Mar 8 at 13:40
Anthony LabarreAnthony Labarre
1,6822033
answered Mar 8 at 13:40
Anthony LabarreAnthony Labarre
1,6822033
answered Mar 8 at 13:40
Anthony LabarreAnthony Labarre
1,6822033
1,6822033
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55063593%2falgorithm-is-it-possible-to-form-a-valid-string%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
I think you can use 2 maps. How large can be
nthough?– vivek_23
Mar 8 at 13:25
@vivek_23 the maximum value of n is approximately in the order of 10^4
– Diefapa
Mar 8 at 13:29
Looks like you will need to use backtracking for this. Because in case of a clash, we can't guarantee which one leads us to a solution consuming all substrings. Also, can a single substring repeat?
– vivek_23
Mar 8 at 13:50
Why does
Example 2have no solution? I seebca+abc=>bcabc, 5 characters from a set of 3 strings. Do we have to use all strings in the set? Must they be used in order?– Prune
Mar 8 at 19:19
@Prune I was under the impression they must overlap exactly on two characters (end + beginning). Hence the OP's example, 'yxz' + 'xzw' = 'yxzw'
– גלעד ברקן
Mar 8 at 19:37