题目:https://www.cnblogs.com/xinz/p/7119695.html

思路:

太晚了,简单说下,先生成图,然后搜索,剪支优化(还没写)

源码(关键部分):golang实现

package main

import (
	"container/list"
	"fmt"
	"longest-word-chain/src/file"
	"longest-word-chain/src/plist"
)

func Do(l *list.List) {
	hc, ec := GetWordHeaderAndEnd(l)
	graph := MakeGraph(hc, ec, l.Len())

	chans := list.New()
	for i := 0; i < len(graph); i++ {
		chanList := list.New()
		chanList.PushBack(plist.GetListValue(l, i))
		visitedArr := make([]bool, l.Len())
		visitedArr[i] = true
		for j := 0; j < len(graph); j++ {
			if graph[i][j] == 1 && i != j && visitedArr[j] != true {
				visitedArr[j] = true
				chanList.InsertBefore(plist.GetListValue(l, j), chanList.Back())
			}
		}
		for k := 0; k < len(graph); k++ {
			if graph[k][i] == 1 && i != k && visitedArr[k] != true {
				visitedArr[k] = true
				chanList.InsertAfter(plist.GetListValue(l, k), chanList.Front())
			}
		}
		if chanList.Front() != nil {
			chans.PushBack(chanList)
		}
	}
	PrintMax(l, chans)
	PrintAll(l, chans)
}

func MakeGraph(headerChars []byte, endChars []byte, lenth int) [][]int {
	graph := make([][]int, lenth)
	for i := 0; i < lenth; i++ {
		graph[i] = make([]int, lenth)
		for j := 0; j < lenth; j++ {
			graph[i][j] = 0
		}
	}
	for i := 0; i < len(headerChars); i++ {
		for j := 0; j < len(endChars); j++ {
			if headerChars[i] == endChars[j] && i != j {
				graph[i][j] = 1
			}
		}
	}

	return graph
}

func GetWordHeaderAndEnd(l *list.List) ([]byte, []byte) {
	headerArr := make([]byte, l.Len())
	endArr := make([]byte, l.Len())
	i := 0
	for item := l.Front(); item != nil; item = item.Next() {
		s := item.Value.(string)
		headerArr[i] = s[0]
		endArr[i] = s[len(s)-1]
		i++
	}
	return headerArr, endArr
}

func PrintAll(l *list.List, chans *list.List) {
	fmt.Print("\n\nPrint all:\n")
	i := 0
	for chan1 := chans.Front(); chan1 != nil; chan1 = chan1.Next() {
		fmt.Printf("%d.", i)
		for item := chan1.Value.(*list.List).Front(); item != nil; item = item.Next() {
			fmt.Printf("%s ", item.Value)
		}
		fmt.Println()
		i++
	}
}

func PrintMax(l *list.List, chans *list.List) {
	lenth := 0
	var maxChan *list.List
	for chan1 := chans.Front(); chan1 != nil; chan1 = chan1.Next() {
		curr := chan1.Value.(*list.List)
		if lenth < curr.Len() {
			lenth = curr.Len()
			maxChan = curr
		}
	}

	file.WriteFileAndCreate("answer", maxChan)

	fmt.Print("\n\nPrint max:\n")
	for item := maxChan.Front(); item != nil; item = item.Next() {
		fmt.Printf("%s ", item.Value)
	}
}

 

完整源码:https://github.com/liujh2010/LearnGolong/tree/master/longest-word-chain

02-11 02:58