微软面试题

Question

Question 2 : Time - 1 hour  You work at a company that works for internet-related technologies based products, and your current project is a spam filter. This filter determines whether or not a string contains spam-like information using a "spam-words-dictionary" (SWD). If an input string contains at least one word from this dictionary as a substring, the filter considers it to be spam-suspicious. (Note: an entire string is considered a substring of itself.)  You've decided to solve a more challenging problem: how many unique strings of length n, composed entirely of lowercase letters, are spam-suspicious for a given SWD? You are given a String[] dictionary, each element of which is a word from the SWD, and an int n. Return the answer modulo 10000.
Definition
Class: SuspiciousStrings
Method: getAmount
Parameters: String[], int
Returns: int
Method signature: int getAmount(String[] dictionary, int n)
(be sure your methodis public)
Notes
"Substring" is formed of consecutive letters (so, it's NOT a subsequence of letters).
"x modulo y" means the remainder of x divided by y.
Constraints
dictionary will contain between 1 and 10 elements, inclusive.
Each element of dictionary will contatin only lowercase letters ('a'-'z').
Each element of dictionary will contain between 1 and 10 characters, inclusive.
n will be between 1 and 2147483647, inclusive.
大家研究研究

Answer 1

没有说是java啊.只是贴出来大家研究研究嘛~!

Answer 2

Does class suspicious string contain an array of strings to analyze?

Answer 3

难度不大，对Pattern数组进行匹配即可，每个Pattern根据spam-words-dictionary分别定义。
更好的方法是提取spam-words-dictionary，组合成更少的匹配模式，再匹配。