1

So I'm not sure how I would approach this so can anyone suggest any algorithms or methods to tackle this problem?

To be more specific, the word cannot be made of the letters of the elements of the periodic table since that would mean the word can always be made up. What I'm asking is whether the word can be made from appending the short forms of the elements.

Also, what would be the run-time of your suggested method?

Sorry if the question is still too vague. I'll edit in case of lack of details.

starcodex
  • 2,198
  • 4
  • 22
  • 34

2 Answers2

2

This is equivalent to segmenting a string into "words", where your "words" are element abbreviations from the periodic table. That article gives a nice long writeup of various solutions. It basically comes down to a dynamic programming problem where you are trying to consume parts of your target string using your elements as pieces.

Rob Neuhaus
  • 9,190
  • 3
  • 28
  • 37
1

A regular expression will do. Just check that your string matches

/(H|He|Li|... all other elements ...)*/i

Regexes can be compiled to have O(N) complexity, where N is the length of input (What is the complexity of regular expression?).

Community
  • 1
  • 1
Koterpillar
  • 7,883
  • 2
  • 25
  • 41
  • I'm still a novice so I haven't worked much with regexes yet. Do you mind elaborating a bit more? – starcodex Mar 23 '13 at 03:31
  • The second sentence is misleading. First, it only applies to "classical regexes". Second, the standard Java implementation of regexes does not use the technology that does this; i.e. Java regexes are not `O(N)` in general. – Stephen C Mar 23 '13 at 03:32
  • Also, the OP's comments imply that he wants the matching to be done case insensitively, and that is going to impact on the performance. – Stephen C Mar 23 '13 at 03:35