The challenge
A Noun Phrase is a phrase that can be replaced by a pronoun [he/she/it].
For example, in the sentence:
a girl ate the cookie
“A girl” is a Noun Phrase, so we can say “she ate the cookie.” “The cookie” is also a Noun Phrase, so we can even say “she ate it.”
Both of these Noun Phrases are made up of an auxialliary (aux) [the/a] followed by a Noun (N) [girl/cookie].
More complicated Noun Phrases can also include an arbitrary number of adjectives (adj). For example:
a big tall scary girl ate the cookie
where “big”, “tall”, and “scary” are all adjectives.
For our simplified model, we will define a Noun Phrase as an auxiliary, followed by 0 or more adjectives, followed by a Noun.
Write a function that takes a sentence (as a string of words separated by spaces), a list of pronouns, and a dictionary (maping words to the grammatical categories aux, adj, and N). Return the sentcnce with all Noun Phrases replaced by pronouns, in the order given.
Assume:
- sentences will contain only lower-case letters and spaces (no puctuation)
- any words not inlcuded in the dictionary are not auxilliaries, adjectives, or nouns
- the number of pronouns provided will be equal to the number of Noun Phrases in the sentence
The solution in Golang
Option 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
package solution
import "strings"
func ReplaceNounPhrases(str string, pro []string, dict map[string]string) string{
words, phrase := strings.Fields(str), ""
state, noun := 0, 0
if len(pro) < 1 {return str}
for _, word := range words {
if _, ok := dict[word]; !ok {state = 0; continue}
if state == 0 && dict[word] != "aux" {continue}
if state == 1 {
if dict[word] == "adj" {phrase += " " + word}
if dict[word] == "N" {
phrase += " " + word
str = strings.Replace(str, phrase, pro[noun], 1)
if noun < len(pro) - 1 {noun++}
state = 0
}
}
if dict[word] == "aux" {state, phrase = 1, word}
}
return str
}
|
Option 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
package solution
import "strings"
func ReplaceNounPhrases(sentence string, pronouns []string, dictionary map[string]string) string {
words, grams, res := strings.Split(sentence, " "), []string{}, []string{}
for _, word := range words { grams = append(grams, dictionary[word]) }
n, i, j, k := len(words), 0, 0, 0
for i<n {
word:=words[i]
if i<n-1 && grams[i]=="aux" {
j = i+1
for j<n && grams[j]=="adj" { j++ }
if j<n && grams[j]=="N" { word = pronouns[k]; k++; i = j+1 } else { i++ }
} else { i++ }
res = append(res, word)
}
return strings.Join(res, " ")
}
|
Option 3:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
package solution
import "strings"
func ReplaceNounPhrases(sentence string, pronouns []string, dictionary map[string]string) string {
words := strings.Split(sentence, " ")
aux := -1
var pronoun int
for i := 0; i < len(words); i++ {
if _, ok := dictionary[words[i]]; !ok {
aux = -1
} else if dictionary[words[i]] == "aux" {
aux = i
} else if dictionary[words[i]] == "N" && aux != -1 {
left := append(words[:aux], pronouns[pronoun])
right := words[aux+i-aux+1:]
words = append(left, right...)
pronoun++
aux = -1
i = aux
}
}
return strings.Join(words, " ")
}
|
Test cases to validate our solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
package solution_test
import (
. "github.com/onsi/ginkgo"
. "github.com/onsi/gomega"
)
var dictionary = map[string]string{
"a": "aux",
"the": "aux",
"girl" : "N",
"cookie" : "N",
"big" : "adj",
"tall" : "adj",
"scary" : "adj",
}
var _ = Describe("Test Example", func() {
It("#1", func() {
Expect(ReplaceNounPhrases("a girl", []string{"she"}, dictionary)).To(Equal("she"))
})
It("#2", func() {
Expect(ReplaceNounPhrases("a girl ate the cookie", []string{"she", "it"}, dictionary)).To(Equal("she ate it"))
})
It("#3", func() {
Expect(ReplaceNounPhrases("a a a big big a cookie", []string{"it"}, dictionary)).To(Equal("a a a big big it"))
})
It("#4", func() {
Expect(ReplaceNounPhrases("a scary girl", []string{"she"}, dictionary)).To(Equal("she"))
})
It("#5", func() {
Expect(ReplaceNounPhrases("a big tall scary girl ate the big cookie", []string{"she", "it"}, dictionary)).To(Equal("she ate it"))
})
})
|
