因为每个组合的字符串,至少要有3个index。 起点,中间拼接点,结点。所以可以将字符串分解为子字符串,判断子字符串是否存在。但是,后面字符串的存在必须要在前面字符串已经存在基础上判断。
class Solution {
public: vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
//使用set容器将所有字符串存起了,因为set有count函数可以查找元素是否存在
set<string> s(words.begin(),words.end());
vector<string> res; for(int i=;i<s.size();i++)
{
string w=words[i];
int n=w.size();
//定义一个数组存标记是否当前位置之前的字符串能找到
int * dp=new int[n+]();
//string的第一个位置之前为空,因此置为1
dp[]=;
for(int j=;j<n;j++)
{
//在当前位置之前的substring都能找到的情况下,才需要考虑后面的string
if(dp[j]==) continue;
for(int k=j+;k<=n;k++)
{
//如果从当前位置到某个位置的字符串能找到,将标记置为1
//k-j<n 不能少,少了可能将字符串自己看为自己的子字符串。
// substr(i,k-j), i 为起始位置,k-j为个数,最大的个数为n,因此k从i+1 到n。
if(k-j<n&&s.count(w.substr(j,k-j))) dp[k]=;
}
if(dp[n])
{
res.push_back(w);
break;
}
}
}
return res;
} };
substr (startpos, length); startpos是起始字符的符号,length为从 startpos开始取的字符串的长度,包括startpos。
动态数组初始化:
对于内置数据类型元素的数组,必须使用() 来显式初始化,否则程序不执行初始化操作。
int * p= new int[10];//每个元素都没有初始化,p指向的int值是不确定的
int * p=new int[10]();//每个元素初始化为0
类类型初始化,如果显式定义无参的构造函数,则调用都调用无参构造函数:
class A
{
public:
int a;
A()
{
a=;
}
};
A *m =new A();
A *n = new A;
cout<<m->a<<endl;
cout<<n->a<<endl;
都输出1
类类型,如果没有显式定义无参的构造函数,则调用默认构造函数:
class A
{
public:
int a; };
int main()
{
A *m =new A();
A *n = new A;
cout<<m->a<<endl;
cout<<n->a<<endl;
}
输出
0
8132528
因为内部数据类型int 加() 才能初始化。
string *psa = new string[10]; // 每个元素调用默认构造函数初始化
string *psa = new string[10](); // 每个元素调用默认构造函数初始化
输出都为空,因为string 类有无参的构造函数。
声明只是表示一个对象的引用,比如我们的语句:
MyClasee myclass;//这个是在栈上创建一个类对象 程序退出其作用域后自动调用类的析构函数.
这里是一个空引用,而通过new关键字可以实例化一个MyClasee的实例,
所以语句:
myclass = new MyClass();//这个是在堆上创建一个类对象, 必须手动delete释放对象 否则会造成内存泄露的.
他的生存期就是他所处的语句块(也就是离他最近的一对{}),离开了他的生存期他就失效了,一般声明形式就是在栈中定义的。堆上的空间需要你用new申请,用delete或者delete[]归还,在进程的范围内,该内存的生存期就完全由你操作了;
当显式定义了一个构造函数之后,系统设定的default empty construct(默认构造函数)不存在了。尤其是定义了有参数的构造函数之后,必须定义一个无参的构造函数,否则A a; 或者A * a=new A;或A * a=new A() 不能通过编译。