1<<-DOC
 2Given an array strings, determine whether it follows the sequence given in the patterns array.
 3In other words, there should be no i and j for which strings[i] = strings[j] and patterns[i] ≠ patterns[j]
 4or for which strings[i] ≠ strings[j] and patterns[i] = patterns[j].
 5
 6Example
 7
 8For strings = ["cat", "dog", "dog"] and patterns = ["a", "b", "b"], the output should be
 9areFollowingPatterns(strings, patterns) = true;
10For strings = ["cat", "dog", "doggy"] and patterns = ["a", "b", "b"], the output should be
11areFollowingPatterns(strings, patterns) = false.
12Input/Output
13
14[time limit] 4000ms (rb)
15[input] array.string strings
16
17An array of strings, each containing only lowercase English letters.
18
19Guaranteed constraints:
201 ≤ strings.length ≤ 105,
211 ≤ strings[i].length ≤ 10.
22
23[input] array.string patterns
24
25An array of pattern strings, each containing only lowercase English letters.
26
27Guaranteed constraints:
28patterns.length = strings.length,
291 ≤ patterns[i].length ≤ 10.
30
31[output] boolean
32
33Return true if strings follows patterns and false otherwise.
34DOC
35
36describe "are_following_patterns" do
37  <<-THINK
38  { cat: :a, dog: :b } X
39  { a: :cat, b: :dog } X
40  { a: [0], b: [1, 2] } X
41  { a: [cat], b: [nil, dog, doggy]
42  THINK
43  def following_patterns?(strings, patterns)
44    return false if strings.size != patterns.size
45    items = Hash.new { |hash, key| hash[key] = [] }
46
47    patterns.each_with_index do |pattern, index|
48      items[pattern][index] = strings[index]
49    end
50
51    true
52  end
53
54  def following_patterns?(strings, patterns)
55    return false if strings.size != patterns.size
56    x_s, x_p = Hash.new { |h, k| h[k] = [] }, Hash.new { |h, k| h[k] = [] }
57
58    strings.each_with_index { |string, index| x_s[string].push(index) }
59    patterns.each_with_index { |pattern, index| x_p[pattern].push(index) }
60
61    return false if x_s.keys.size != x_p.keys.size
62    strings.each_with_index do |string, index|
63      return false if x_s[string] != x_p[patterns[index]]
64    end
65
66    patterns.each_with_index do |pattern, index|
67      return false if x_p[pattern] != x_s[strings[index]]
68    end
69    true
70  end
71
72  def following_patterns?(strings, patterns)
73    k, m = {}, {}
74    i, j = 0, 0
75    strings.map { |s| k[s] ||= (i += 1) } == patterns.map { |p| m[p] ||= (j += 1) }
76  end
77
78  [
79    { strings: ["cat", "dog", "dog"], patterns: ["a", "b", "b"], x: true },
80    { strings: ["cat", "dog", "doggy"], patterns: ["a", "b", "b"], x: false },
81    { strings: ["cat", "dog", "dog"], patterns: ["a", "b", "c"], x: false },
82    { strings: ["aaa"], patterns: ["aaa"], x: true },
83    { strings: ["aaa", "aaa", "aaa"], patterns: ["aaa", "bbb", "aaa"], x: false },
84    { strings: ["aaa", "aab", "aaa"], patterns: ["aaa", "aaa", "aaa"], x: false },
85    { strings: ["re", "jjinh", "rnz", "frok", "frok", "hxytef", "hxytef", "frok"], patterns: ["kzfzmjwe", "fgbugiomo", "ocui", "gafdrts", "gafdrts", "ebdva", "ebdva", "gafdrts"], x: true },
86    { strings: ["kwtfpzm", "kwtfpzm", "kwtfpzm", "kwtfpzm", "kwtfpzm", "wfktjrdhu", "anx", "kwtfpzm"], patterns: ["z", "z", "z", "hhwdphhnc", "zejhegjlha", "xgxpvhprdd", "e", "u"], x: false },
87    { strings: ["ato", "ato", "jflywws", "ato", "ato", "se", "se", "kiolm", "wizdkdqke"], patterns: ["ofnmiqelt", "ofnmiqelt", "flqmwoje", "ofnmiqelt", "zdohw", "jyk", "ujddjtxt", "s", "kw"], x: false },
88    { strings: ["syf", "syf", "oxerkx", "oxerkx", "syf", "xgwatff", "pmnfaw", "t", "ajyvgwd", "xmhb", "ajg", "syf", "syf", "wjddgkopae", "fgrpstxd", "t", "i", "psw", "wjddgkopae", "wjddgkopae", "oxerkx", "zf", "jvdtdxbefr", "rbmphtrmo", "syf", "yssdddhyn", "syf", "jvdtdxbefr", "funnd", "syf", "syf", "wd", "syf", "vnntavj", "wjddgkopae", "yssdddhyn", "wcvk", "wjddgkopae", "fh", "zf", "gpkdcwf", "qkbw", "zf", "teppnr", "jvdtdxbefr", "fmn", "i", "hzmihfrmq", "wjddgkopae", "syf", "vnntavj", "dung", "kn", "qkxo", "ajyvgwd", "fs", "kanixyaepl", "syf", "tl", "yzhaa", "dung", "wa", "syf", "jtucivim", "tl", "kanixyaepl", "oxerkx", "wjddgkopae", "ey", "ai", "zf", "di", "oxerkx", "dung", "i", "oxerkx", "wmtqpwzgh", "t", "beascd", "me", "akklwhtpi", "nxl", "cnq", "bighexy", "ddhditvzdu", "funnd", "wmt", "dgx", "fs", "xmhb", "qtcxvdcl", "thbmn", "pkrisgmr", "mkcfscyb", "x", "oxerkx", "funnd", "iesr", "funnd", "t"], patterns: ["enrylabgky", "enrylabgky", "dqlqaihd", "dqlqaihd", "enrylabgky", "ramsnzhyr", "tkibsntkbr", "l", "bgtws", "xwuaep", "o", "enrylabgky", "enrylabgky", "e", "auljuhtj", "l", "d", "jfzokgt", "e", "e", "dqlqaihd", "fgglhiedk", "nj", "quhv", "enrylabgky", "oadats", "enrylabgky", "nj", "zwupro", "enrylabgky", "enrylabgky", "pyw", "enrylabgky", "bedpuycdp", "e", "oadats", "i", "e", "fobyfznrxm", "fgglhiedk", "irxtd", "oyvf", "fgglhiedk", "ebpp", "nj", "p", "d", "cufxylz", "e", "enrylabgky", "bedpuycdp", "mitzb", "shsnw", "papmvh", "bgtws", "chtp", "pze", "enrylabgky", "klp", "wpx", "mitzb", "fo", "enrylabgky", "bvcigrirhe", "klp", "pze", "dqlqaihd", "e", "iufunacwjo", "bubgww", "fgglhiedk", "og", "dqlqaihd", "mitzb", "d", "dqlqaihd", "mysidv", "l", "naj", "clftmrwl", "fjb", "zjjnrffb", "sh", "gcn", "ouispza", "zwupro", "c", "rdank", "chtp", "xwuaep", "jufhm", "iyntbgm", "sufs", "mkivpe", "bxdd", "dqlqaihd", "zwupro", "vzxbbculgv", "zwupro", "l"], x: true },
89  ].each do |x|
90    it do
91      result = following_patterns?(x[:strings], x[:patterns])
92      expect(result).to eql(x[:x])
93    end
94  end
95end