I have a long list of strings and I'm trying to find a more efficient way of removing those elements that are prefixes of another:

example = {"Clothing", "Clothing/Accessories", "Clothing/Accessories/Belts", 
   "Watches", "Watches/Accessories", "Watches/Accessories/Pocket Watch Chains"}

This is what I have, but it is not very optimized:

DeleteCases[example, a_ /; Or @@ Table[
     StringStartsQ[b, a], {b, DeleteCases[example, a]}]]
 {"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"} 

My real example has 13,732 strings and it takes 292.156 seconds to pare it down to 11,372.

  • 1
    $\begingroup$ You could try StringSplit and work with DeleteDuplicates or similar from there. $\endgroup$
    – Yves Klett
    Commented Jun 9, 2016 at 19:15
  • 1
    $\begingroup$ What if there is a "Watch" string, should it be considered already included in "Watches" or should we only care about keys between / as a whole? $\endgroup$
    – Kuba
    Commented Jun 9, 2016 at 19:45

5 Answers 5


Get the relation graph of your example

graph = SimpleGraph[RelationGraph[StringStartsQ, example], 
  VertexLabels -> "Name"]

Get the end of the vertex in every weaky connected graph


{"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}

Hope this can help. :)

  • 1
    $\begingroup$ +1 for pretty, but this will be deadly slow on a large list... $\endgroup$
    – ciao
    Commented Jun 10, 2016 at 6:24
  • $\begingroup$ @ciao Good point out.Because of the RelationGraph is a bug function will result a ton wasteful computation.And I have reposted to Wolfram Research but get no response. $\endgroup$
    – yode
    Commented Jun 10, 2016 at 6:27

Your solution doesn't seem to work when there are duplicates. Anyway, could you test the performance of the following method?

example =  RandomChoice[{"Clothing", "Clothing/Accessories", 
  "Clothing/Accessories/Belts", "Watch", "Watches/Accessories", 
  "Watches/Accessories/Pocket Watch Chains"

Split[Sort@example,  StringStartsQ[#2, #] &][[;; , -1]] // AbsoluteTiming
  {"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}}

In case where you want to care about keys between / as a whole, e.g. Watch to not be considered within Watches, you can use:

StringStartsQ[#2 <> "/", # <> "/"]

instead of

StringStartsQ[#2, #]
  • $\begingroup$ It's 2.43905 seconds, much much better! $\endgroup$
    – user5601
    Commented Jun 9, 2016 at 20:17

EDIT: My original answer, while quite a bit quicker than the current answer, dropped some words that should not be dropped, as does the other current answer, e.g.. {"pa","paperweight"} fails on both (unless that is the intent of the OP, which I doubt).

This led me to the following, which does not suffer from the problem and is also quite a bit quicker yet:

dumpPrefixes2 = DeleteCases[#, Alternatives @@ Flatten@StringCases[#, (a : __ ~~ "/" :> a)]] &;




wrds = WordList[];

example = 
   NestList[StringJoin[{#, "/", RandomSample[wrds, 1]}] &, 
    RandomChoice[wrds], RandomChoice[{3, 2, 1} -> {0, 1, 2}]], 20000]

to generate a test set, seemed to perform well on loungebook, perhaps @kuba or you can test with your data on a real machine...

  • $\begingroup$ You mean that pa should not be considered included in paperweight because it's not up to /? That's why I've asked OP in a comment. Untill I get the answer I'm going hard merging :) $\endgroup$
    – Kuba
    Commented Jun 10, 2016 at 5:14
  • $\begingroup$ Yes, that's what I meant. Examples are like inventory items and categories, things like "watch" and "watchdog" then present a problem... $\endgroup$
    – ciao
    Commented Jun 10, 2016 at 5:21
  • $\begingroup$ Yep. Added those cases handler too, can't test now but it seems that StringStartsQ[#2 <> "/", # <> "/"] should be enough. $\endgroup$
    – Kuba
    Commented Jun 10, 2016 at 5:31
  • $\begingroup$ p.s. there seem to be a problem with handling duplicates by dumpPrefixes, this dumpPrefixes2@{"Watch", "Watch"} returns the input. Have I missed something? $\endgroup$
    – Kuba
    Commented Jun 10, 2016 at 5:33
  • $\begingroup$ @Kuba - no, since OP did not specify behavior for duplicates, I did not remove them: goal was to be able to get result, and keep it stable (that is, in the order of the target list). Raises the question of what's to be done if duplicates are in list (they may not be), but trivially handled by a DeleteDuplicates pre/post operation. None of these may be issue for OP (and unless there are many lists or changing lists, who cares about performance?), I just found it an interesting tuning problem, posted idea. $\endgroup$
    – ciao
    Commented Jun 10, 2016 at 6:16
Last /@ Gather[example, StringStartsQ[#2, #]&]

{"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}

FileNameJoin /@ Last /@ Gather[FileNameSplit /@ example, SubsetQ[#2, #] &]

{"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}

Also: slow but worth considering: a variation on @yode's approach

GraphComputation`SourceVertexList@SimpleGraph@RelationGraph[StringStartsQ, example]

{"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}


GeneralUtilities`GraphSources @ SimpleGraph @ RelationGraph[StringStartsQ, example]

{"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}


containerStrings[stringList_] := Module[{TF, pos},
   TF = Outer[StringContainsQ, #, #]\[Transpose] &[stringList];
   pos = Position[Tally /@ TF, {{__}, {True, 1}}];
   Extract[stringList, pos]

{"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}

It is yet to be tested whether Outer is efficient for a large list of strings.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.