這題看了別人討論才做出來(lái)。
暴力法：枚舉所有的矩形，然后統(tǒng)計(jì)各個(gè)矩形中的字符數(shù)。這樣時(shí)間復(fù)雜度O(n^12)必然超時(shí)。
可以反過(guò)來(lái)考慮問(wèn)題，對(duì)于矩形中的每一個(gè)單元，會(huì)有多少個(gè)矩形包含它。
這樣思考，問(wèn)題就很簡(jiǎn)單了：
一個(gè)矩形可以由它的左上角和右下角唯一決定。
而若某單元(x,y)包括在某矩形中，那么，這個(gè)矩形的左上角(x',y')必然為(0<=x'<=x),(0<=y'<=y).
右上角(x'',y'')必然為(x<=x''<c),(y<=y''<r).c為總列數(shù),r為總行數(shù)。
這樣的矩形顯然有(x+1)(y+1)(c-x)(c-y)個(gè)。(坐標(biāo)均為0-based)
代碼如下：
???class?SubrectanglesOfTable
??????????????{?
??????????????public:?
??????????????vector<long?long>?getQuantity(vector?<string>?t)?
??????????????????{?
??????????????????????????vector<long?long>?res(26);???
??????????????????????????
??????????????????????????for(int?i=0;i<t.size();++i)
?????????????????????????????? t[i]+=t[i];
??????????????????????????
??????????????????????????int?tmp?=?t.size();
??????????????????????????for(int?i=0;i<tmp;++i)
????????????????????????????t.push_back(t[i]);???????????????????????????????
????????????????????????????
??????????????????????????int?r?=?t.size();
??????????????????????????int?c?=?t[0].size();
??????????????????????????
??????????????????????????for(int?i=0;i<r;++i)
???????????????????????????? for(int?j=0;j<c;++j){
??????????????????????????????????res[?t[i][j]-'A']+=(i+1)*(j+1)*(r-i)*(c-j);???????????????
??????????????????????????????????}???
?????????????????????????????
????????????????????????? return?res;???????????????????????????????? ???????????????????????????????
??????????????????}
｝
其實(shí)不需要生成字符串的四個(gè)拷貝。